是否有一种贪心算法可以为非分数（0-1背包）背包问题提供最优解？我知道对于背包问题的分数版本，存在一种可以给出最优解的贪心算法。
贪心算法解决0-1背包问题
4
- fatma.ekici
4
可能没有。我说"可能"是因为你可以用无限多种贪心算法来解决它（考虑到你可以按照任何可能的函数对2个参数（重量和成本）进行排序）。我所知道的最好的贪心0-1背包算法可以保证让你接近最优解的50%。如果它们都具有相同的重量或者相同的价值，那么贪心算法将给出最优解。 - Bernhard Barker
@Dukeling：你能否提供一下贪心算法的链接或描述一下（保证50%最优解）？ - aplavin
1我在斯坦福大学Coursera免费在线课程中看到了50%的最优贪心解法。同一讲师提供了此处的视频（请查看“19.近似算法”）。此处似乎有一篇相关文章。 - Bernhard Barker
由于0/1背包问题是NP难问题，因此任何问题的多项式时间贪心算法都将证明P = NP。因此，任何贪心算法都必须在伪多项式或指数时间内运行。 - templatetypedef
1个回答
8
即使使用贪心算法可以解决分数背包问题，但是在0-1背包问题中没有可行的贪心算法。
这是因为在0-1背包问题中，你只能要么拿走该物品的全部，要么完全不取该物品，而在分数背包问题中，如果你的背包已满，你可以只取部分物品。 这一点非常关键。
下面是一个反驳贪心算法适用于0-1背包问题的例子。 假设你有一个大小为6的背包和以下物品：
物品 价值 大小 价值/大小
A 5.5 4 1.38
B 4 3 1.33
C 4 3 1.33
对于0-1背包问题，如果你试图使用贪心算法，你会始终选择具有最高价值/大小比的物品，也就是物品A。 在取走物品A后，你只有2或更小尺寸的物品空间，所以你不能再拿任何其他物品了。 那意味着你背包里唯一的东西就是物品A，总价值为22。
另一方面，如果你没有贪心地选择最有价值的物品，而是选择了物品B，然后你就有足够的空间来取物品C。 这将导致背包中的总价值为24，比贪心算法更好。
这是因为在0-1背包问题中，你只能要么拿走该物品的全部，要么完全不取该物品，而在分数背包问题中，如果你的背包已满，你可以只取部分物品。 这一点非常关键。
下面是一个反驳贪心算法适用于0-1背包问题的例子。 假设你有一个大小为6的背包和以下物品：
物品 价值 大小 价值/大小
A 5.5 4 1.38
B 4 3 1.33
C 4 3 1.33
对于0-1背包问题，如果你试图使用贪心算法，你会始终选择具有最高价值/大小比的物品，也就是物品A。 在取走物品A后，你只有2或更小尺寸的物品空间，所以你不能再拿任何其他物品了。 那意味着你背包里唯一的东西就是物品A，总价值为22。
另一方面，如果你没有贪心地选择最有价值的物品，而是选择了物品B，然后你就有足够的空间来取物品C。 这将导致背包中的总价值为24，比贪心算法更好。
- Arararagi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接