knapsack.go

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
}