文档介绍：第4章贪心算法
贪心算法概念与基本要素
(1)最优子结构性质
(2)贪心选择性质
贪心算法与动态规划算法的差异
应用范例
(1)活动安排问题
(2)哈夫曼编码
(3)最优装载问题
(4)单源最短路径
(5)最小生成树
(6)多机调度问题
贪心算法概念与基本要素
目标:问题形式化表示、比较不同求解方法效率
付款问题
有5元、2元、1元、5角、2角、1角的货币多张,假设每种面值的货币的张数都足够多,需要找给客户4元6角
问题:如何挑选合适的币值及其张数,使得付给客户的货币总张数最少?
多种答案:
4元6角= 2元*2 + 5角*1 + 1角*1 ——4张
4元6角= 1元*4 + 2角*2 + 1角*2 ——8张
………..
可以采用多种方法求解此问题:枚举、分治、动态规划、贪心
问题的形式化表示
输入:
1)可用币值及其张数
2张5元、 2张2元、 4张1元、 4张5角、 4张2角、 4张1角
Available=(5, 2, 1, , , )
N=(n5元, n2元, n1元, n5角, n2角, n1角)
=(2, 2, 4, 4, 4, 4)
2)应付款总数:X = 4元6角
输出/解向量:
支付的币种及其张数
解向量X=(x5元, x2元, x1元, x5角, x2角, x1角)
X1=(x5元, x2元, x1元, x5角, x2角, x1角)
=(0, 2, 0, 1, 0, 1) 4
X2=(x5元, x2元, x1元, x5角, x2角, x1角)
=(0, 0, 4, 0, 2, 2) 8
约束:
1)已支付数应等于应支付数:
5*x5元+ 2* x2元+ 1*x1元+
* x5角+ *x2角+ * x1角
= X=4元6角
2)每种货币支付的张数不超过该货币总张数:
x5元≤n5元, x2元≤n2元, x1元≤n1元
x5角≤ n5角, x2角≤ n2角, x1角≤ n1角
优化目标:
支付的货币总张数最少
对可行解X=(x5元, x2元, x1元, x5角, x2角, x1角),
min (x5元+ x2元+ x1元+ x5角+ x2角+ x1角)
枚举法求解:
1. 在满足约束2—支付张数限制的前提下,考虑解向量X中各分量xi的各种组合,i= 5元, 2元, 1元, 5角, 2角, 1角,得到1个可能解
X=(x5元, x2元, x1元, x5角, x2角, x1角)
注: N=(n5元, n2元, n1元, n5角, n2角, n1角)
=(2, 2, 4, 4, 4, 4)时,共有
(2+1)* (2+1)* (4+1)* (4+1)* (4+1)* (4+1)* (4+1)种组合
2. 判断每种可能解X=(x5元, x2元, x1元, x5角, x2角, x1角)是否满足约束1——支付总额,从中选出可行解
3. 从可行解中选出货币总张数最少者,作为最优解
分治法求解
4元6角
2元3角
2元3角
2元
3角
2元
3角
1元
2角
1元
x2元=1
X1角=3
1角
X1角=1
5角
x1元=1
分治法求解本问题时的难点:
1)如果只采用1种固定的划分方法,有可能得不到解
始终采取2等分方式
4元6角 2元3角 1元1角5分??!!
2)采用多种问题划分方法,不同划分导致不同可行/部分解
划分1:一分为二/2等分
划分2:m元n角 m元+ n角
2)分治法比较难处理最优化问题
由于带有最优化要求,需要考虑多种划分方法、可行解
算法效率
动态规划求解法
x2元=1
2元
x2元=2
4元
x5元=0
0元
满足约束的部分底层最小子问题
底层最小子问题:对币值为i的单种货币,分别取0,1,…, ni张货币
x1元=2
2元
x1元=4
4元
.。。。
X5角=1
X5角=4
2元
.。。。
X2角=1
X1角=1
4元
存在问题:各种规模的子问题及其组合的数目太多,求解费时耗力
4元
10
贪心方法求解
原理:
1) 自上而下,逐步构造、扩展货币支付解向量
X=(x5元, x2元, x1元, x5角, x2角, x1角)
初始( ?, ? , ?, ?, ?, ? )
Step1. ( 0, ?, ?, ?, ? ?)
Step2. ( 0, 2, ?, ?, ? ?)
Step3. ( 0, 2, 0, ?, ? ?)
Step4. ( 0, 2, 0,