使用分数背包方法解决背包问题

Question

有两个著名的背包问题：

1）给定n个物品，每个物品有其重量和成本。我们需要选择物品，将其装入我们的背包中，并使其总成本最大化。可以使用动态规划轻松解决。

2）分数背包：与第一个问题相同，但我们不仅可以取整个物品，还可以取其一部分。这个问题可以使用贪心算法轻松解决。

假设我们使用第二个问题的贪心算法来解决第一个问题。我该如何证明，我们得到的解决方案不会比最优解差两倍以上？

- Aleksandr Tukallo

---

“Worse”是什么意思？ - Juan Lopes

你可能会有更多的限制，因为一般情况下（权重、成本是双精度值，而不仅仅是整数值），并不能很好地使用 DP 算法。 - Alexander Anikin

@Alexander Anikin：int并不是限制条件-只需扩大规模，使用体积为1e100的背包；物品A的重量为1，成本为1，物品B的重量为1e100，成本为1e100-1。 - Dmitry Bychenko

Answer 1

据我所见，贪心算法的解决方案可以尽可能低效。假设你有一个容量为 1 的背包和两个（n = 2）物品：

item weight cost density
------------------------
   A      ε    ε       1  <- greedy choice
   B      1  1-ε     1-ε  <- optimal choice

贪心算法会选择花费 ε 的方案 A，而最优解则是选择花费 1-ε 的方案 B。所以贪心算法选择了（贪心）的解决方案。

  (1-ε)/ε = 1/ε - 1 

比最优解低效ε倍，想要ε=1e-100的效果也可以，但会导致贪心算法非常低效。 编辑：如果只有整数值，请按比例缩放上面的示例：您有一个容量为X的背包和两个（n = 2）物品。

item weight cost density
------------------------
   A      1    1       1  <- greedy choice
   B      X  X-1   1-1/X  <- optimal choice

在这种情况下，贪心算法的解决方案是：

   (X - 1) / 1 = X - 1

相对于最优解，效率可能会降低数倍。最后，将 X 设置得足够大（如 X = 1e100）

- Dmitry Bychenko

---

是的，真正的2-竞争贪心算法需要考虑仅由具有分数设置的项组成的解决方案。 - David Eisenstat

是的，谢谢！我明白了，它也适用于整数。感谢您提供的好的反例！ - Aleksandr Tukallo

@Dmitry Bychenko：非常简洁的答案！ - Codor

@Aleksandr Tukallo：欢迎！即使只有一个项目（即B）无法分割，您仍可以创建具有任意大的低效性的反例。即使B可以分割，但不能分成足够小的块（我们无法将金原子分成金质子和中子），您也可以创建反例。 - Dmitry Bychenko

可能相关，但回答不够简洁：http://stackoverflow.com/questions/35967159/continuous-knapsack-vs-0-1-knapsack - Codor