是否有任何贪婪算法可以为非小数（0-1背包）背包问题提供最佳解决方案？我知道有一个适用于Knapsack的分数版本，可以提供最佳解决方案。
对于0-1背包而言，没有贪婪的算法，即使贪婪适用于Fractional Knapsack。
这是因为在0-1背包中你要么拿走所有物品，要么你根本不拿这个物品，不像分数背包你可以在你的包包溢出时拿走一件物品。这很关键。
这是一个证明Greedy算法适用于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，这比贪婪的路线更好。