2022-04-18：things是一个N*3的二维数组，商品有N件，商品编号从1~N， 比如things[3] = [300, 2, 6]， 代表第3号商品：

package main

import "fmt"

func main() {
	money := 1000
	size := 5
	things := [][][]int{{{800, 2, 0}}, {{400, 5, 1}}, {{300, 5, 1}}, {{400, 3, 0}}, {{500, 2, 0}}}
	n := clean(things, size)
	fmt.Println(n)
	ans := maxScore(things, n, money)
	fmt.Println(ans)
}

func clean(things [][][]int, size int) int {
	for i := 0; i < size; i++ {
		cur := things[i][0]
		if cur[2] != 0 {
			things[i] = make([][]int, 0)
			things[cur[2]] = append(things[cur[2]], cur)
		}
	}
	n := 0
	for i := 0; i < size; i++ {
		if len(things[i]) > 0 {
			things[n] = things[i]
			n++
		}
	}
	return n
}

func maxScore(things [][][]int, n, money int) int {
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, money+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j <= money; j++ {
			dp[i][j] = -2
		}
	}
	return process(things, n, 0, money, dp)
}

func process(things [][][]int, n, index, rest int, dp [][]int) int {
	if rest < 0 {
		return -1
	}
	if index == n {
		return 0
	}
	if dp[index][rest] != -2 {
		return dp[index][rest]
	}
	project := things[index]
	a := project[0]
	var b []int
	if len(project) > 1 {
		b = project[1]
	}
	var c []int
	if len(project) > 2 {
		c = project[2]
	}
	p1 := process(things, n, index+1, rest, dp)
	p2 := process(things, n, index+1, rest-a[0], dp)
	if p2 != -1 {
		p2 += a[0] * a[1]
	}
	p3 := -1
	if b != nil {
		p3 = process(things, n, index+1, rest-a[0]-b[0], dp)
	}
	if p3 != -1 {
		p3 += a[0]*a[1] + b[0]*b[1]
	}
	p4 := -1
	if c != nil {
		p4 = process(things, n, index+1, rest-a[0]-c[0], dp)
	}
	if p4 != -1 {
		p4 += a[0]*a[1] + c[0]*c[1]
	}
	p5 := -1
	if c != nil {
		p5 = process(things, n, index+1, rest-a[0]-b[0]-c[0], dp)
	}
	if p5 != -1 {
		p5 += a[0]*a[1] + b[0]*b[1] + c[0]*c[1]
	}
	ans := getMax(getMax(getMax(p1, p2), getMax(p3, p4)), p5)
	dp[index][rest] = ans
	return ans
}

func getMax(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}