动态规划求解背包问题：代码输出异常（得300而非预期220）

嘿，我发现你的背包DP代码里藏着一个很容易踩的Python坑，导致结果不对。让我给你拆解一下：

你得到300而不是预期的220，核心原因是DP表的初始化方式错误，导致所有行共享同一个列表的引用，完全打乱了动态规划的状态转移逻辑。

具体哪里错了？ #

看这行初始化代码：

K = [[0] * (W+1)] * (n+1)

在Python中，[x] * k 并不会创建k个独立的x副本，而是创建k个指向同一个x的引用。这里[0]*(W+1)是一个列表，然后*(n+1)只是把这个列表的引用复制了n+1次。也就是说，K[0]、K[1]...K[n]其实都是同一个列表的别名——当你修改K[i][w]时，所有行的第w列都会跟着变！

怎么修复？ #

把初始化改成用列表推导式，这样每一行都是独立的新列表：

K = [[0]*(W+1) for _ in range(n+1)]

修复后的完整代码 #

def knapsack_dynamic(ws, vs, W):
    n = len(ws)
    # 用列表推导式创建独立的子列表，避免引用共享
    K = [[0]*(W+1) for _ in range(n+1)]
    for i in range(n+1):
        for w in range(W+1):
            if i == 0 or w == 0: # 背包为空或无可用容量时价值为0
                K[i][w] = 0
            else:
                if ws[i-1] > w:
                    # 当前物品重量超过容量，只能不选
                    K[i][w] = K[i-1][w]
                else:
                    # 选或不选当前物品，取最大值
                    K[i][w] = max(vs[i-1] + K[i-1][w-ws[i-1]], K[i-1][w])
    return K[n][W]

# 测试验证
maxw = 50
ws = [10, 20, 30]
vs = [60, 100, 120]
print(knapsack_dynamic(ws, vs, maxw)) # 现在会正确输出220

为什么之前会算出300？ #

因为所有行共享同一列表，当你处理每个物品时，修改的其实是同一个底层列表。最终K[n][W]实际上把所有物品的价值加在了一起（60+100+120=300），而不是按照DP逻辑选择最优的组合（20+30重量对应100+120价值，总和220）。

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