2 个容量相同的背包 - 为什么我们不能两次找到最大值
2 knapsacks with same capacity - Why can't we just find the max-value twice
如果给你一组具有价值和重量的物品：[(w1,v2),(w2,v2),...(wn,vn)]，以及两个容量相等的背包 Knap1 和 Knap2 C，目标是确定物品S1和S2的最优子集分别是什么可以进入Knap1和Knap2并最大化背包的价值和容量。
解决此问题的错误方法是首先使用 DP 编程算法使用所有项目作为候选项填充 Knap1，然后使用 Knap1 的剩余项目填充 Knap2。
我不明白如果两个背包的容量相等，为什么这个算法是不正确的。有人可以解释一下或举个例子吗？
假设背包的容量是10，我们有这些物品（重量，价值）：
(8, 200)
(1, 10)
(1, 10)
(2, 15)
(9, 100)
只看一个背包的贪心算法会使用重量为 8、1 和 1 的物体来获得 220 值，但是当你考虑到两个袋子时，显然留下 1 并取 2 更好。
一个反例:
项目 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
如果给你一组具有价值和重量的物品：[(w1,v2),(w2,v2),...(wn,vn)]，以及两个容量相等的背包 Knap1 和 Knap2 C，目标是确定物品S1和S2的最优子集分别是什么可以进入Knap1和Knap2并最大化背包的价值和容量。
解决此问题的错误方法是首先使用 DP 编程算法使用所有项目作为候选项填充 Knap1，然后使用 Knap1 的剩余项目填充 Knap2。
我不明白如果两个背包的容量相等，为什么这个算法是不正确的。有人可以解释一下或举个例子吗？
假设背包的容量是10，我们有这些物品（重量，价值）：
(8, 200) (1, 10) (1, 10) (2, 15) (9, 100)
只看一个背包的贪心算法会使用重量为 8、1 和 1 的物体来获得 220 值，但是当你考虑到两个袋子时，显然留下 1 并取 2 更好。
一个反例:
项目 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