经典0-1背包问题memoization记忆化实现输出异常排查

问题复现 #

• 原始无缓存递归实现的0-1背包逻辑正确，测试用例参数为weight=[1,2,3,4,5,6]、value=[4,5,6,7,8,9]，遍历容量0、2、4、6、8、10、12、14、16、18、20共11组输入，输出结果依次为0、5、10、15、17、22、24、26、31、33、35
• 新增记忆化缓存后，同参数下输出结果为0、5、10、15、20、25、30、35、40、45、50，容量≥8时结果明显偏大，和预期不符

根因定位 #

问题出在dp缓存数组的初始化语句：

a.dp = [[-1] * (20 + 2)] * (len(weight) + 2)

Python中对嵌套列表使用*做乘法复制时，不会为外层的每一行创建独立的内层列表副本，所有行索引指向的是同一个内存地址的列表对象。这就导致你给dp[n][crr_cap]写入缓存值时，所有行对应容量位置的值都会被同步篡改，缓存命中逻辑完全失效，最终返回错误的累加结果。

可以用几行简单代码验证这个特性：

test_dp = [[-1]*3]*2
test_dp[0][1] = 100
print(test_dp)
# 输出为[[-1, 100, -1], [-1, 100, -1]]，两行对应位置同时被修改

修复方法 #

替换dp数组的初始化逻辑，用列表推导式为每一行生成独立的内层列表，避免引用共用问题：

a.dp = [[-1]*(20+2) for _ in range(len(weight)+2)]

替换后缓存会按照(已考虑物品数n, 剩余容量crr_cap)的二维索引独立存储计算结果，记忆化逻辑可以正常运行，输出结果会和原始无缓存递归版本完全一致。

优化建议：不建议将缓存容量上限硬编码为20，可以在getMaximumvalue方法内部根据传入的capacity参数动态初始化dp数组，适配不同规模的输入。

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