algorithm - 0-1背包的贪心算法

Question

是否有任何贪心算法可以为非分数（0-1 背包）背包问题提供最佳解决方案？我知道有一个分数版本的背包可以提供最佳解决方案。

Answer 1

尽管贪心算法适用于分数背包，但没有适用于 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，这比贪婪路线要好。