计算机算法设计与分析(第3版)[王晓东编著][电子教案第4章(19)

计算机算法设计与分析(第3版)[王晓东编著][电子教案

4.2 贪心算法的基本要素对于0-1背包问题，贪心选择之所以不能得到最优解 是因为在这种情况下，它无法保证最终能将背包装满，部 分闲臵的背包空间使每公斤背包空间的价值降低了。事实 上，在考虑0-1背包问题时，应比较选择该物品和不选择 该物品所导致的最终方案，然后再作出最好选择。由此就 导出许多互相重叠的子问题。这正是该问题可用动态规划 算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解01背包问题。