算法设计与分析-4课案.ppt

  1. 1、本文档共108页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 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)

希望之星 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档