连续背包vs. 0-1背包 [英] Continuous Knapsack Vs. 0-1 Knapsack

问题描述

为什么贪婪方法在连续背包问题上有效，而同一种方法在0-1背包问题上无效？

Why does Greedy approach work on continuous knapsack problem whereas the same approach does not work for the 0-1 knapsack problem?

推荐答案

对于连续背包，您不能将 q> 0 最优解决方案中每单位成本 c 的商品，而 q’> 0 价格为 c’>的另一个项目c 。否则，您只需将第一项的 min（q，q'）金额替换为第二项的相同金额，从而使总成本增加 min（ q，q'）*（c'-c）。

For continuous knapsack, you can't have q > 0 of an item with the cost c per unit in an optimal solution, while leaving q' > 0 of an another item with the cost c' > c. Otherwise, you simply replace min(q, q') amount of the first item with the same amount of the second, increasing total cost by min(q,q')*(c' - c).

对于0-1背包，其中有一个朴素贪婪算法的反例。考虑重量为 6、5、4 且价格为 8、5、4 的物品。允许总重量为 9 。显然，最佳解决方案是采用第二和第三项的总成本为 9 ，但第一项的绝对值和重量均值更高，因此应通过贪婪算法选择。

For 0-1 knapsack, where is a counterexample for a naive greedy algorithm. Consider items with weight 6, 5, 4 and cost 8, 5, 4. Let the total allowed weight be 9. Clearly, optimal solution is to take the second and third items for the total cost of 9, but the first item is worth more, both in absolute value and relative to its weight, so should be selected by `greedy' algorithm.

这篇关于连续背包vs. 0-1背包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！