- 1、本文档共108页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第4章 贪心算法
贪心算法概念与基本要素
(1)最优子结构性质
(2)贪心选择性质
贪心算法与动态规划算法的差异
应用范例
(1)活动安排问题
(2)哈夫曼编码
(3)最优装载问题
(4)单源最短路径
(5)最小生成树
(6)多机调度问题
贪心算法概念与基本要素
目标:问题形式化表示、比较不同求解方法效率
E.g.1 付款问题
有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, 0.5, 0.2, 0.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元 +
0.5* x5角 + 0.2*x2角+ 0.1* 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种固定的划分方法,有可能得不到解
e.g 始终采取2等分方式
4元6角 ? 2元3角 ? 1元1角5分??!!
2)采用多种问题划分方法,不同划分导致不同可行/部分解
划分1:一分为二/2等分
划分2:m元n角 ? m元 + n角
2)分治法比较难处理最优化问题
由于带有最优化要求,需要考虑多种划分方法、可行解
? 算法效率
动态规划求解法
满足约束的部分底层最小子问题
底层最小子问题:对币值为i的单种货币,分别取0,1,…, ni张货币
.。。。
.。。。
存在问题:各种规模的子问题及其组合的数目太多,求解费时耗力
10
贪心方法求解
原理:
1) 自上而下,逐步构造、扩展货币支付解向量
X=
文档评论(0)