如果给你一组具有值和重量的物品：[(w1,v2),(w2,v2),...(wn,vn)]，以及两个容量相等的背包 Knap1 和 Knap2 C，则目标是确定可以分别放入 Knap1 和 Knap2 的物品 S1 和 S2 的最佳子集，并最大化背包的价值和容量。
解决此问题的错误方法是首先使用 DP 编程算法使用所有项目作为候选项来填充 Knap1，然后使用 Knap1 中剩余的项目来填充 Knap2。
我不明白如果两个背包的容量相等，为什么这个算法是不正确的。有人可以解释一下或者举个例子吗？
A 反例:
项目集 S：(w_i, v_i)
s_1=(1,2) , s_2=(2,1) , s_3=(3,10) , s_4=(4,7)
背包容量：c_1 = c_2 = 5
你的第一轮 DP 会拿走这些物品s_1 and s_3这将导致价值12。现在对于第二个背包，有s_4 and s_2左边。因此你的算法将选择s_4这将导致价值7. s_2将被剩下。
总价值：19
最佳解决方案是s_1 and s_4在一个背包里，并且s_2 and s_3在另一个。
最佳总价值：20
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
