Skip to content

Instantly share code, notes, and snippets.

@fernandoporazzi
Last active August 29, 2015 14:21
Show Gist options
  • Save fernandoporazzi/012d3196effa790ab800 to your computer and use it in GitHub Desktop.
Save fernandoporazzi/012d3196effa790ab800 to your computer and use it in GitHub Desktop.
package main
import "fmt"
// Cria estrutura
type item struct {
string
w, v int
}
// Cria um array de objetos
var wants = []item{
{"Math Book", 10, 150},
{"English Book", 5, 35},
{"Geography Book", 1, 20},
{"Portuguese Book", 4, 20},
}
func main() {
items, w, v := knapsack(len(wants)-1, 15) // Passa penúltimo índice como parâmetro
fmt.Println(items)
fmt.Println("weight:", w)
fmt.Println("value:", v)
}
// {i} = Índice
// {w} = Peso máximo da mochila
// Tipos de retorno: []string, int, int
func knapsack(i, w int) ([]string, int, int) {
if i < 0 || w == 0 {
return nil, 0, 0
} else if wants[i].w > w { // se peso do índice passado for maior que capacidade da mochila
return knapsack(i-1, w)
}
i0, w0, v0 := knapsack(i-1, w) // Chama função recursivamente decrementando o índice atual
i1, w1, v1 := knapsack(i-1, w-wants[i].w) // Chama função recursivamente decrementando o índice e diminuindo o peso pelo peso do índice atual
v1 += wants[i].v // Altera valor de v1 para o valor do íncice atual
if v1 > v0 { // se v1 > v0, retorno objetos, peso e valor total
return append(i1, wants[i].string), w1 + wants[i].w, v1
}
return i0, w0, v0 // Se v0 for maior que v1, retorna suas informações
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment