连续背包Vs。0-1个背包

Question

为什么贪心方法适用于连续背包问题，而不适用于0-1背包问题？

Answer 1

对于连续背包，您不能在最佳解决方案中使用单位成本c的项目q > 0，而将另一个项目的q' > 0留在成本c' > c中。否则，您只需将第一个项目的min(q, q')金额替换为第二个项目的相同数量，从而按min(q,q')*(c' - c)增加总成本。

对于0-1背包，其中是一个朴素贪婪算法的反例。考虑具有weight 6, 5, 4和cost 8, 5, 4的项目。假设总的允许权重为9。显然，最佳解决方案是将第二和第三项作为9的总成本，但第一项无论是绝对值还是相对于其权重都更有价值，因此应使用“贪婪”算法进行选择。

Answer 2

在0-1背包中，贪婪方法不起作用，因为它确实希望你权衡所有可能的组合，因为在分数背包中，我们可以使用贪婪算法来获得最大利润，而空白空间降低了负载的每磅(重量)的有效利润。在0-1背包中，当我们考虑是否在背包中包含一个项目时，我们必须比较包含该项目的子问题的解与排除该项目的子问题的解，然后才能做出选择。

因此，解决方案运行O(nW)，其中n是物品的数量，W是可以放入背包中的物品的权重

希望它能澄清！