main.go

package main

import (
	"fmt"
)

type Set struct {
	weight int
	value  int
}

var (
	W = 80
)

/*  memorize, memo */
type key struct {
	k1, k2 int
}

var dp map[key]int
var s []Set

/* return max value */
/* memorize */
func choice(i, j int) int {
	if v, ok := dp[key{i, j}]; ok {
		fmt.Println("Hit", i, j)
		return v
	}
	if i == len(s) {
		return 0
	}
	if j-s[i].weight < 0 {
		return choice(i+1, j)
	}
	value1 := s[i].value + choice(i+1, j-s[i].weight)
	value2 := choice(i+1, j)
	if value2 > value1 {
		dp[key{i, j}] = value2
		return value2
	}
	dp[key{i, j}] = value1
	return value1
}

func main() {
	dp = make(map[key]int)

	s = []Set{{23, 3}, {14, 2}, {10, 3}, {11, 4}, {52, 20}, {5, 20}, {10, 3}}
	v := choice(0, W)
	fmt.Println(v)
}