fat*_*ici 3 algorithm knapsack-problem combinatorics
是否有任何贪婪算法可以为非分数（0-1 背包）背包问题提供最佳解决方案？我知道有一个小数版本的 Knapsack 给出了最佳解决方案。
尽管贪婪适用于分数背包，但没有 0-1 背包的贪婪算法。
这是因为在 0-1 Knapsack 中，您要么拿走所有物品，要么根本不拿走该物品，而在 Fractional Knapsack 中，如果您的包溢出，您只能拿走其中的一部分。这是至关重要的。
这是一个反驳贪婪算法适用于 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，这比贪婪路线要好。