题解 | #购物单# Go 代码

这题倒霉就倒霉在我一开始没看清题目...金额后面的那个数字按照题意是表示接下来有几个物品, 我前面一直把这个理解成购买物品的个数限制

其实这个题就是个 dp 背包问题, 主要难点还是在题目的理解上, 首先你得排除附件, 先只关注主件, dp[i][j] 的定义就是取到 i 这个主件时, 有 j 这么多的钱的情况下, 能拥有的最大价值是多少

然后再来处理附件问题, i 这个主件在 j 金额下, 只有两种情况, j 金额不够 i 主件的价格, 所以该主件无法购买, 所以 dp[i][j] = dp[i-1][j], 也就是取到前一个主件不取当前主件的时候(金额不变)

当 j > i 主件的价格, 选择根据题意有以下几种, 只取主件, 取主件和附件1, 取主件和附件2, 取主件和附件1+附件2, 然后计算每种情况的最大价值即可, 实际上相比于背包问题原题, 这题的改动就是在这里而已

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

func main() {
    var budget, limit int // 这个定义的 limit 实际上没用, 最开始理解错就在这里
    fmt.Scan(&budget, &limit)
    items := [][]int{}  // 代表主件
    attach := map[int][][]int{}  // 代表附件, 用主件的物品序号取
    no := 1  // 物品序号

    for {
        var price, weight, q int
        n, _ := fmt.Scan(&price, &weight, &q)
        if n == 0 {
            break
        }

        if q == 0 {
		  // 注意这里第三个元素不再是 q 而是 序号, 因为后面需要用主件序号从 attach 中取出它的附件
            items = append(items, []int{price, weight, no})
        } else {
            if attach[q] == nil {
                attach[q] = [][]int{}
            }
            attach[q] = append(attach[q], []int{price, weight, q})
        }
        no++
    }

  // 因为需要观察取到前一个主件的情况(dp[i-1]), 所以 dp 的长度是主件数 +1
    dp := make([][]int, len(items)+1)
    for i := 0; i <= len(items); i++ {
        dp[i] = make([]int, budget+1)
    }

    for i := 1; i <= len(items); i++ {
        for j := 0; j <= budget; j++ {
            if j - items[i-1][0] < 0 {
			  // 说明 这个金额没法购买当前这个组件
                dp[i][j] = dp[i-1][j]
            } else {
			  // 当前金额已经起码足够购买主件本身
			  // cost1,2,3,4 分别代表只买主件的花费, 买主件+附件1 的花费, 买主件+附件2 的花费, 买主件+附件1+附件2 的花费
			  // value代表对应cost的价值
                var cost1, cost2, cost3, cost4 int
                var value1, value2, value3, value4 int

                cost1 = items[i-1][0]
                value1 = items[i-1][0] * items[i-1][1]

                a := attach[items[i-1][2]]
                if a != nil {
				  // 如果这个主件是有配件的, 根据配件数量填入 cost2 ~ 4 的值
				  // 不要在意这一堆 index 的可读性, 我也懒得改了...能看懂就行
                    if len(attach[items[i-1][2]]) > 0 {
                        cost2 = cost1 + attach[items[i-1][2]][0][0]
                        value2 = value1 + attach[items[i-1][2]][0][0] * attach[items[i-1][2]][0][1]
                    }
                    if len(attach[items[i-1][2]]) > 1 {
                        cost3 = cost1 + attach[items[i-1][2]][1][0]
                        value3 = value1 + attach[items[i-1][2]][1][0] * attach[items[i-1][2]][1][1]

                        cost4 = cost3 + cost2 - cost1
                        value4 = value3 + value2 - value1
                    }
                }
				
			  // 只买主件的时候 dp 取值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost1]+value1)
                if j - cost2 >= 0 {
				  // 如果负担得起 cost2, 比较一下最值
                    dp[i][j] = max(dp[i][j], dp[i-1][j-cost2]+value2)
                }
                if j - cost3 >= 0 {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-cost3]+value3)
                }
                if j - cost4 >= 0 {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-cost4]+value4)
                }
            }
        }
    }

    fmt.Println(dp[len(items)][budget])
}