为什么贪婪方法适用于连续背包问题而不适用于 0-1 背包问题？
最佳答案
对于连续背包，您不能在最佳解决方案中拥有每单位成本 c 的 q > 0 元素，同时保留 q' > 0 另一个项目，成本为 c' > c。否则，您只需将第一个项目的 min(q, q') 数量替换为第二个项目的相同数量，从而将总成本增加 min(q,q')*(c' -c).
对于 0-1 背包，其中是朴素贪心算法的反例。考虑重量为 6, 5, 4 且成本为 8, 5, 4 的元素。让允许的总重量为9。显然，最佳解决方案是选择第二个和第三个项目的总成本为 9，但是第一个项目无论是绝对值还是相对于其重量都更有值(value)，因此应该通过`贪心算法。
关于algorithm - 连续背包与连续背包0-1 背包，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35967159/