❖例如，如果一套钱币设计合理，则最 小兑现问题就满足贪婪选择性质
2.2 最优子结构性质
❖最优子结构是指：一个问题的最优解 中包含它的子问题的最优解
❖例如，用合理的一套钱币实现最小兑 现问题，就满足最优子结构性质
❖当钱币面值是10、5、1时，要兑现26， 则可以用{10、10、5、1}实现。第一步 实现（取10）后，剩余问题的最优解是 {10、5、1}，是整个问题最优解的子集， 满足最优子结构性质
2. 贪婪法要满足的性质
用贪婪法解决问题时，并不能保证它能找到最 优解。但是，当问题满足下面两个性质时，贪 婪法可以找到问题的最优解。
2.1 贪婪选择性质 2.2 最优子结构性质
2.1 贪婪选择性质
❖贪婪选择性质是指：所求问题的全局 最优解，可以通过一系列的局部最优的 选择来达到
❖每进行一次选择，就得到一个局部的 解，并把所求解的问题简化为一个规模 更小的类似子问题
对任务3，找到当前花费最小的人员b∊{b, d}; -- 10
对任务4，找到当前花费最小的人员d∊{d}; -- 14
贪婪法解决任务分配问题的时间复杂度是O(n2)
4. 贪婪法完全成功解决的例子
4.1 连续背包问题 4.2 单源最短路径问题 4.3 Kruskal算法求解最小生成树 4.4 Prim算法求解最小生成树 4.5 钓鱼问题
❖三个贪心算法的复杂度都是O(nlogn)，都不能确保 求得最优解
3.4 任务分配问题
任务1 9 6 5 7
任务2 2 4 8 6
任务3 7 3 1 9
任务4 8 7 8 4
人员a 人员b 人员c 人员d
对任务1，找到当前花费最小的人员c∊{a, b, c, d};--5
对任务2，找到当前花费最小的人员a∊{a, b, d}; -- 7
3 30
结点4：60
4.2.4 Dijkstra算法内存操作示例
0
10
100
10
1
30 4 100
10
-1 1
50
11
∞
2
1
60 20 30 3
-1 -1 1 1 1
0 10 ∞ 30 100 0 10 60 30 100
4.2.5 Dijkstra算法复杂度分析
Dijkstra算法是典型的贪婪算法 Dijkstra算法的时间复杂度是O(n2) Dijkstra算法的空间复杂度是O(n)
第5章 贪婪法
1. 贪婪法概述 2. 贪婪法要满足的性质 3. 贪婪法不完全成功解决的例子 4. 贪婪法完全成功解决的例子
1. 贪婪法概述
❖贪婪法只根据当前已有信息做出最佳选择。一 旦作出选择，不管将来有什么结果，这个选择 都不会改变
❖贪婪法并不是从整体考虑最优，而是局部考虑 最优
❖因为不需要整体考虑贪婪法的效率通常较高
3. 贪婪法不完全成功解决的例 子
3.1 最短多段路径问题 3.2 货郎担问题 3.3 0-1背包问题 3.4 任务分配问题
3.1 最短多段路径问题
4
02
3
19
8
8
27
8
4
37
45
6 8
56
77 9
6
83
65
❖在每一阶段查找下一步路径选择的最小值
❖时间复杂度是O(kn)，n是阶段总数，k是 每一阶段节点总数的最大值
4.1 连续背包问题
❖背包总容量为42，三个物品的价值/重量分别为： 40/3， 101/31，67/10，物品可以分割。步骤：
（1）背包中全部放入物品1，当前价值为40，所占重 量为3；
（2）背包中全部放入物品3，当前价值是107，所占 重量为3+10=13。
（3）背包中放入物品2的重量为29，当前价值是 107+101/31*29 = 201.48。
3.2 货郎担问题
a
2
b
31
73
c
8
d
一条最优路径是： a -> b -> d -> c -> a，
路径总长为16
❖从任意一节点出发，选择 该节点相邻的、没有被遍 历的、不形成回路的最近 节点
❖例如，a -> b -> c ->d 路 径总长为18
❖贪婪法求解TSP问题的时 间复杂度是O(n2)
3.3 0-1背包问题
4.2.3 Dijkstra算法示例(选择3)
00
10
90
100
10
50
结点2：60
60
结点3：30
50 60 2
20
3 30
结点4：100
min(60, 30, 100) = 30, 故选择结点3。然后修改由于3所 属集合的变化而引起的各点当前最短距离变化
4.2.3 Dijkstra算法示例(选择2)
0
10
100
1
30 4
10
50
60
2
20
3
4.2.2 Dijkstra算法原理
➢Dijkstra提出的算法把所有顶点分为两类： 已知点集和未知点集
➢该算法的思路是：按路径长度的递增次序, 逐步产生最短路径的算法。首先求出长度 最短的一条最短路径，再参照它求出长度 次短的一条最短路径，依次类推，直到从 顶点v到其它各顶点的最短路径全部求出为 止
4.2.3 Dijkstra算法示例(初始化)
0
0
10
100
10
1
30 4 100
10
50
60
2
∞
20
3
30
4.2.3 Dijkstra算法示例(选择1)
00
10
100
10
1
30 4 100
10
50
60
60 ∞ 2
20
3 30
min(10, ∞ 30, 100) = 10, 故选择结点1。然后修改由于1 所属集合的变化而引起的各点当前最短距离变化
0 10
60
100
10
1
30
90
4
10
结点2：50 结点4：90
50
50 2
20
60 3 30
min(50, 90) = 50, 故选择结点2。然后修改由于2所属集 合的变化而引起的各点当前最短距离变化
4.2.3 Dijkstra算法示例(选择4)
0
10
100
10
1
30
60
4
10
50
60
50 2
20
❖背包总容量为42，三个物品的价值/重量分别为： 40/3， 101/31，67/10。有3种贪婪解法：
（1）按照性价/重比从大到小选择。这种方式的在连 续背包问题中能够求得最优解。本问题的结果是107
（2）按照价值从大到小选择。本问题的结果是168。
（3）按照重量从小到大选择。本问题的结果是107。
❖贪婪法解决连续背包问题的复杂度是O(nlogn)
4.2 单源最短路径问题
4.2.1 连续背包问题 4.2.2 单源最短路径问题 4.2.3 Dijkstra算法示例 4.2.4 Dijkstra算法内存操作示例 4.2.5 Dijkstra算法复杂度分析
4.2.1 问题描述
求有向图某点（0）到其他各点的最短路径