2022-04-18：things是一个N*3的二维数组，商品有N件，商品编号从1~N，

比如things[3] = [300, 2, 6]，

代表第3号商品：价格300，重要度2，它是6号商品的附属商品，

再比如things[6] = [500, 3, 0]，

代表第6号商品：价格500，重要度3，它不是任何附属，它是主商品，

每件商品的收益是价格*重要度，花费就是价格，

如果一个商品是附属品，那么只有它附属的主商品购买了，它才能被购买，

任何一个附属商品，只会有1个主商品，

任何一个主商品的附属商品数量，不会超过2件，

主商品和附属商品的层级最多有2层。

给定二维数组things、钱数money，返回整体花费不超过money的情况下，最大的收益总和。

答案2022-04-18：

本来想用rust写的，但老是编译不通过，实在没辙。

代码用golang编写。代码如下：

 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
}
}  

执行结果如下：

***

[左神java代码](