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

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

4.2 贪心算法的基本要素

背包问题：与0-1背包问题类似，所不同的是在选择物品i装 入背包时，可以选择物品i的一部分，而不一定要全部 装入背包，1≤i≤n。

这2类问题都具有最优子结构性质，极为相似，但 背包问题可以用贪心算法求解，而0-1背包问题却不能 用贪心算法求解。