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

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