algorithm - 连续背包比。 0-1 背包

Question

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

Answer 1

对于连续背包，在最佳解决方案中，您不能有 q > 0 的每单位成本为 c 的元素，同时留下 q' > 0 成本为 c' > c 的另一项。否则，您只需将第一项的 min(q, q') 数量替换为第二项的相同数量，将总成本增加 min(q,q')*(c' - c).

对于 0-1 背包，哪里是朴素贪婪算法的反例。考虑重量为 6, 5, 4 和成本为 8, 5, 4 的项目。让总允许重量为 9。显然，最佳解决方案是将 9 的总成本取第二和第三项，但第一项的值(value)更高，无论是绝对值还是相对于它的权重，所以应该选择 `贪心算法。