用分数背包法求解背包

Question

有两个著名的背包问题：

1) 给定 n 个项目，每个项目都有其 weight 和 cost。我们需要 select 件物品，这些物品将适合我们的背包，并且总计成本最高。使用dynamic programming.

即可轻松解决

2) 分式背包：与第一种相同，但不能只带整件，只能带一部分。使用 greedy algorithm.

可以轻松解决此问题

假设我们正在使用第二个问题中的 greedy algorithm 来解决第一个问题。我如何证明，我们将获得的解决方案不会比最佳解决方案差两倍？

Answer 1

据我所知，贪婪的解决方案可以尽可能低效。假设您有一个容量为 1 的背包和两个 (n = 2) 件物品：

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

所以当最优解是以 1-ε 的成本获得 B。选择的（贪心）解决方案是

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

比最佳效率低

倍。使 ε 尽可能少（例如，ε = 1e-100）并且有一个非常低效的贪婪解决方案。

编辑：如果只有整数值，只需scale上面的示例：你有一个容量为[=22=的背包] 和两个 (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）

Solving knapsack with fractional knapsack approach