带两个背包的0-1背包问题的反例

Question

我在这课程中遇到了以下问题：

考虑背包问题的一个变式，其中我们有两个背包，具有整数容量1和2。像往常一样，给出了带正值和正整数权的项。我们希望选择1,2的子集，使1和1的总权重分别最多为1和2。假设每件物品都装在背包里。考虑以下两种算法方法。 (1)利用讲座中的算法，为第一个背包选择一个最大值可行解1，然后在剩下的项目上再次运行，为第二个背包选择一个最大值可行解2。 (2)对容量为1+2的背包，采用自学习算法选取最大值可行解，然后将所选项目分解为两组1+2，其大小分别为1和2。 下列哪一种说法是正确的？

1. 算法(1)保证了对原问题提供1=2的最优可行解。
2. 算法(1)保证对原问题产生最优可行解，但算法(2)没有。
3. 算法(2)保证对原问题产生最优可行解，但算法(1)不是。
4. 这两种算法都不能保证对原问题产生最优可行解。

“讲课算法”是在YouTube上完成的。6OF8X6HQ，这是一个袋子的0-1背包问题.

这个问题的正确答案是选项4。这、这和这 post给出了问题的解决方案。然而，我很难找到相反的例子，表明选项1到3是不正确的。你能举个例子吗？

编辑：可接受的答案没有为选项1提供反例，请参见两个容量相同的背包-为什么我们不能两次找到最大值？。

Answer 1

(Weight; Value): (3;10), (3;10), (4;2)容量7，3

第一个方法在第一个袋子中选择3+3，其余的项不适合第二个sack。

(Weight; Value): (4;10), (4;10), (4;10), (2:1)容量6，6

第二种方法选择(4+4+4)，但这套方法不能不损失地放入两个袋子中，而(4+2)和(4)则更好。