2个容量相同的背包 - 为什么我们不能只找到两次最大值

Question

如果给你一组具有值和重量的项目:[(w1,v2),(w2,v2),...(wn,vn)],以及两个容量相等的背包Knap1和Knap2,目标是确定可以分别进入Knap1和Knap2的项目S1和S2的最佳子集是什么,并最大化背包的值和容量.

解决这个问题的一种不正确的方法是首先使用所有项目作为候选项的DP编程算法填充Knap1,然后使用Knap1中的剩余项目填充Knap2.

我不明白为什么如果两个背包具有相同的容量,这个算法是不正确的.有人可以解释或举例吗？

Answer 1

一个反例:
设置项目的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,s_3这将导致价值12.现在第二个背包,有s_4和s_2离开.因此,您的算法将选择s_4哪个会产生价值7.s_2将遗留下来.
总价值:19

最佳的解决办法是s_1和s_4一个背包,并s_2与s_3在其他.最佳总价值:20

Answer 2

假设背包的容量是10,我们有这些物体(重量,值):

(8,200)(1,10)(1,10)(2,15)(9,100)

只看一个背包的贪婪算法会使用重量为8,1和1的物体得分为220,但是当你认为两个麻袋明显离开1并且拿2时更好.