关于0/1背包问题动态规划实现代码生成表格与《算法图解》示例表格差异的技术咨询

问题背景 #

我正在学习动态规划，持有《Grokking Algorithms》（《算法图解》）一书，书中的0/1背包问题示例使用如下物品价值与重量：价值数组为[1500, 2000, 3000]，重量数组为[1, 3, 4]，背包容量W=4。运行书中提供的0/1背包问题Python实现代码后，得到的动态规划表格输出如下：

+---+------+------+------+------+
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1500 | 1500 | 1500 | 1500 |
| 0 | 1500 | 1500 | 2000 | 3500 |
| 0 | 1500 | 1500 | 2000 | 3500 |
+---+------+------+------+------+

最终得到的最大价值3500是正确的，但生成的该动态规划表格与书中示例展示的表格并不一致，我怀疑这个正确结果可能是巧合。现咨询：该代码生成的表格与书中表格存在差异的原因是什么？是否是因为代码使用的递推公式与书中的公式存在实际效果上的不同？

附书中给出的Python实现代码：

# A Dynamic Programming based Python 
# Program for 0-1 Knapsack problem 
# Returns the maximum value that can 
# be put in a knapsack of capacity W 
from tabulate import tabulate 
def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
    # Build table K[][] in bottom up manner 
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0 
            elif wt[i - 1] <= w: 
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]) 
            else: 
                K[i][w] = K[i - 1][w] 
    print(tabulate(K, tablefmt="pretty")) 
    return K[n][W] 
# Driver code 
val = [1500, 2000, 3000] 
wt = [1, 3, 4] 
W = 4 
n = len(val) 
print(knapSack(W, wt, val, n))

解答 #

别担心，这个正确结果绝对不是巧合！表格差异的核心原因是物品的处理顺序不同，而代码的递推公式完全符合0/1背包的标准逻辑，和书中的公式本质一致。

1. 物品顺序是表格差异的直接原因

《算法图解》中的0/1背包示例物品顺序是：

• 吉他：重量1，价值1500
• 音响：重量4，价值3000
• 笔记本电脑：重量3，价值2000

而你代码里的物品顺序是：

• 物品1：重量1，价值1500
• 物品2：重量3，价值2000
• 物品3：重量4，价值3000

动态规划表格的每一行对应“前i个物品”的最优解集合，物品顺序不同，中间行的计算过程自然会不一样：

• 你代码的第2行（i=2）是处理完前两个物品（1kg+3kg）的结果，当容量为4时，最优解是1500+2000=3500；
• 当处理第3个物品（4kg，3000）时，容量4的情况下，放入它的价值（3000）不如前两个物品的组合（3500），所以第3行的容量4单元格直接继承了上一行的3500，这就导致第2、3行的容量4值相同。

而书中的顺序下，第2行（i=2）是处理完吉他+音响的结果，容量4的最优解是3000；处理第3个物品（笔记本，3kg）时，容量4可以放下笔记本+吉他（1500+2000=3500），比上一行的3000更优，所以第3行的容量4值会更新为3500，这就和你的表格呈现出差异。

2. 递推公式完全符合书中逻辑，结果正确是必然的

你代码里的核心公式：

K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])

完全对应0/1背包的核心思想，和书中的公式没有本质区别：

• 当当前容量w能装下第i个物品（对应数组索引i-1）时，比较两种选择的价值：
  • 放入该物品：物品价值 + 剩余容量w - wt[i-1]下前i-1个物品的最优解
  • 不放入该物品：直接继承前i-1个物品在容量w下的最优解
• 取两者的最大值作为当前状态的最优解；装不下时则直接继承上一行的结果。

0/1背包的最优解和物品的处理顺序无关，所以不管你按什么顺序处理物品，最终的最大价值都是正确的。

验证：调整物品顺序后表格会和书中一致

如果你把代码里的val和wt换成书中的顺序：

val = [1500, 3000, 2000]
wt = [1, 4, 3]

运行代码后得到的表格就会和书中的示例完全一致，最终结果依然是3500。

内容的提问来源于stack exchange，提问作者Robin Andrews