两个背包的 0-1 背包问题的反例
Counter examples for 0-1 knapsack problem with two knapsacks
我在 this 课程中遇到了以下问题：
Consider a variation of the Knapsack problem where we have two
knapsacks, with integer capacities 1 and 2. As usual, we are given
items with positive values and positive integer weights. We want to
pick subsets 1,2 with maximum total value such that the total weights of 1 and 1 are at most 1 and 2, respectively. Assume that every item fits in either knapsack. Consider the following two algorithmic approaches.
(1) Use the algorithm from lecture to pick a max-value feasible solution 1 for the first knapsack, and then run it again on the remaining items to pick a max-value feasible solution 2 for the second knapsack.
(2) Use the algorithm from lecture to pick a max-value feasible solution for a knapsack with capacity 1+2, and then split the chosen items into
two sets 1+2 that have size at most 1 and 2, respectively.
Which of the following statements is true?
Algorithm (1) is guaranteed to produce an optimal feasible solution to the original problem provided 1=2.
Algorithm (1) is guaranteed to
produce an optimal feasible solution to the original problem but
algorithm (2) is not.
Algorithm (2) is guaranteed to produce an
optimal feasible solution to the original problem but algorithm (1) is
not.
Neither algorithm is guaranteed to produce an optimal feasible
solution to the original problem.
"algorithm from lecture" 在 YouTube 上。 https://www.youtube.com/watch?v=KX_6OF8X6HQ，也就是一个包0-1的背包问题
此问题的正确答案是选项 4。This, this and post 提出问题的解决方案。但是，我很难找到表明选项 1 到 3 不正确的反例。你能举出什么吗？
编辑：
接受的答案没有为选项 1 提供反例；请参阅 。
(Weight; Value): (3;10), (3;10), (4;2)
容量 7、3
第一种方法选择3+3放入第一个袋子，剩余的物品不适合第二个袋子
(Weight; Value): (4;10), (4;10), (4;10), (2:1)
容量 6, 6
第二种方法选择了(4+4+4)，但是这个集合不能不损失地装进两个麻袋，而(4+2)和(4)更好
我在 this 课程中遇到了以下问题：
Consider a variation of the Knapsack problem where we have two knapsacks, with integer capacities 1 and 2. As usual, we are given items with positive values and positive integer weights. We want to pick subsets 1,2 with maximum total value such that the total weights of 1 and 1 are at most 1 and 2, respectively. Assume that every item fits in either knapsack. Consider the following two algorithmic approaches.
(1) Use the algorithm from lecture to pick a max-value feasible solution 1 for the first knapsack, and then run it again on the remaining items to pick a max-value feasible solution 2 for the second knapsack.
(2) Use the algorithm from lecture to pick a max-value feasible solution for a knapsack with capacity 1+2, and then split the chosen items into two sets 1+2 that have size at most 1 and 2, respectively.
Which of the following statements is true?
Algorithm (1) is guaranteed to produce an optimal feasible solution to the original problem provided 1=2.
Algorithm (1) is guaranteed to produce an optimal feasible solution to the original problem but algorithm (2) is not.
Algorithm (2) is guaranteed to produce an optimal feasible solution to the original problem but algorithm (1) is not.
Neither algorithm is guaranteed to produce an optimal feasible solution to the original problem.
"algorithm from lecture" 在 YouTube 上。 https://www.youtube.com/watch?v=KX_6OF8X6HQ，也就是一个包0-1的背包问题
此问题的正确答案是选项 4。This, this and
编辑：
接受的答案没有为选项 1 提供反例；请参阅
(Weight; Value): (3;10), (3;10), (4;2)
容量 7、3
第一种方法选择3+3放入第一个袋子，剩余的物品不适合第二个袋子
(Weight; Value): (4;10), (4;10), (4;10), (2:1)
容量 6, 6
第二种方法选择了(4+4+4)，但是这个集合不能不损失地装进两个麻袋，而(4+2)和(4)更好