algorithm - 用分数背包法求解背包

Question

有两个著名的背包问题:

1) 给定n 项，每个项都有其权重 和成本。我们需要选择适合我们背包且总成本最高的元素。使用动态规划可以轻松解决。

2) Fractional knapsack: 和第一个一样，但是我们不能只带整个元素，而是可以带一部分。这个问题可以用贪心算法轻松解决。

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

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)，并且有一个非常低效的贪婪解决方案。

编辑:如果只有整数值，只需缩放上面的示例:你有一个容量为 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)