算法分析与设计：03 第三讲 贪心算法.pdf

: .
化为规模更小的子问题。
9 ——《算法分析与设计》
0-1背包问题
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，
背包最大承载重量为C。应如何选择装入背包的物品，使得
装入背包中物品的总价值最大?
在选择装入背包的物品时，对每种物品i只有2种选择，
即装入背包或不装入背包。不能将物品i装入背包多次，
也不能只装入物品i的一部分。
背包问题：
与0-1背包问题类似，所不同的是在选择物品i装入背包时，
可以选择物品i的一部分，而不一定要全部装入背包，
1≤i≤n。
10 Warning : .
——《算法分析与设计》
第三讲 贪心算法
 贪心算法的基本要素
 活动安排问题
 最优装载
 单源最短路径
 哈夫曼编码
 多机调度问题
11 Warning : .
——《算法分析与设计》
第三讲 贪心算法
 贪心算法的基本要素
 活动安排问题
 最优装载
 单源最短路径
 哈夫曼编码