普及讲座6基于贪心的算法和应用举例C版.pptx
《普及讲座6基于贪心的算法和应用举例C版.pptx》由会员分享,可在线阅读,更多相关《普及讲座6基于贪心的算法和应用举例C版.pptx(34页珍藏版)》请在咨信网上搜索。
1、江苏省大丰高级中学江苏省大丰高级中学 陈鹏陈鹏Peng ChenPeng Chen JiangSu DaFeng Senior High School JiangSu DaFeng Senior High School基于贪心的算法和应用举例GreedyGreedySelector Selector AlgorithmAlgorithm&A&Applicationpplication一贪心策略二应用举例三小结15 四月四月 20242一贪心策略引例引例1 1删数问题删数问题 键盘输入一个高精度的正整数键盘输入一个高精度的正整数n n(n=240n=240),去),去掉其中任意掉其中任意s s个
2、数字后剩下的数字按原左右次序将组个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的成一个新的正整数。编程对给定的n n和和s s,寻找一种方,寻找一种方案,使得剩下的数字组成的新数最小。案,使得剩下的数字组成的新数最小。【算法分析算法分析】每一步总是选择一个使剩下的数最小的数字删去,每一步总是选择一个使剩下的数最小的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字;否则删除第一个递减区间的首字符。除最后一个数字;否则删除第一个递减区间的首字符。15 四月四月 20243一贪心策略定义定义贪心贪心 贪心算法是从问题
3、的某一个初始状态出发,通过贪心算法是从问题的某一个初始状态出发,通过逐步构造最优解的方法向给定的目标前进,并期望通逐步构造最优解的方法向给定的目标前进,并期望通过这种方法产生出一个全局最优解的方法。过这种方法产生出一个全局最优解的方法。小球表示当前状态;小球表示当前状态;红箭头表示当前最优决策;红箭头表示当前最优决策;蓝箭头表示其他决策。蓝箭头表示其他决策。15 四月四月 20244方向方向一贪心策略 贪心标准选择贪心标准选择:所谓贪心标准选择就是应用当前:所谓贪心标准选择就是应用当前“最好最好”的标准作为统一标准,将原问题变为一个相的标准作为统一标准,将原问题变为一个相似的但规模更小的子问题
4、,而后的每一步都是当前看似的但规模更小的子问题,而后的每一步都是当前看似最佳的选择。似最佳的选择。最优子结构最优子结构:当一个问题的最优解包含其子问题:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。的最优解时,称此问题具有最优子结构性质。15 四月四月 20245一贪心策略引例引例2 2金银岛金银岛 某天某天KIDKID利用飞行器飞到了一个金银岛上,上面利用飞行器飞到了一个金银岛上,上面有许多珍贵的金属,有许多珍贵的金属,KIDKID喜欢各种宝石的艺术品,可喜欢各种宝石的艺术品,可是也不拒绝这样珍贵的金属。但是他只带着一个口袋,是也不拒绝这样珍贵的金属。但是他只带着一个
5、口袋,口袋至多只能装重量为口袋至多只能装重量为w w的物品。岛上金属有的物品。岛上金属有s s个种类个种类,每种金属重量不同,分别为每种金属重量不同,分别为n n1 1,n n2 2,n ns s,同时,同时每个种类的金属总的价值也不同,分别为每个种类的金属总的价值也不同,分别为v v1 1,v v2 2,v vs s。KIDKID想一次带走价值尽可能多的金属,问他最想一次带走价值尽可能多的金属,问他最多能带走价值多少的金属。多能带走价值多少的金属。注意注意到金属是可以被任意到金属是可以被任意分割的,并且金属的价值和其重量成正比。分割的,并且金属的价值和其重量成正比。15 四月四月 20246
6、一贪心策略【算法分析算法分析】有以下几种策略可供选择:有以下几种策略可供选择:(1 1)每次挑选价值最大的物品装入背包,得到的)每次挑选价值最大的物品装入背包,得到的结果是否最优?结果是否最优?(2 2)每次挑选所占重量最小的物品装入是否能得)每次挑选所占重量最小的物品装入是否能得到最优解?到最优解?(3 3)每次选取单位重量价值最大的物品。)每次选取单位重量价值最大的物品。15 四月四月 20247一贪心策略 解题一般步骤解题一般步骤:1 1、设计数据找规律;、设计数据找规律;2 2、进行贪心猜想;、进行贪心猜想;3 3、正确性证明(严格证明和一般证明)、正确性证明(严格证明和一般证明)一般
7、证明一般证明:列举反例;:列举反例;严格证明严格证明:数学归纳和反证法;:数学归纳和反证法;4 4、程序实现。、程序实现。15 四月四月 20248二应用举例例例1 1三国游戏三国游戏【问题描述问题描述】小涵很喜欢一个叫做三国的游戏。在游戏中,小涵小涵很喜欢一个叫做三国的游戏。在游戏中,小涵和计算机各执一方,组建各自的军队进行对战。游戏中共和计算机各执一方,组建各自的军队进行对战。游戏中共有有N N位武将(位武将(N N为偶数且不小于为偶数且不小于4 4),任意两个武将之间有一),任意两个武将之间有一个个“默契值默契值”,表示若此两位武将作为一对组合作战时,表示若此两位武将作为一对组合作战时,
8、该组合的威力有多大。游戏开始前,所有武将都是自由的该组合的威力有多大。游戏开始前,所有武将都是自由的(称为自由武将,一旦某个自由武将被选中作为某方军队(称为自由武将,一旦某个自由武将被选中作为某方军队的一员,那么他就不再是自由武将了),换句话说,所谓的一员,那么他就不再是自由武将了),换句话说,所谓的自由武将不属于任何一方。游戏开始,小涵和计算机要的自由武将不属于任何一方。游戏开始,小涵和计算机要从自由武将中挑选武将组成自己的军队,规则如下:小涵从自由武将中挑选武将组成自己的军队,规则如下:小涵先从自由武将中选出一个加入自己的军队,然后计算机也先从自由武将中选出一个加入自己的军队,然后计算机也
9、从自由武将中选出一个加入计算机方的军队。从自由武将中选出一个加入计算机方的军队。15 四月四月 20249二应用举例 接下来一直按照接下来一直按照“小涵小涵计算机计算机小涵小涵”的顺序选的顺序选择武将,直到所有的武将被双方均分完。然后,程序自动择武将,直到所有的武将被双方均分完。然后,程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武,拥有更高默契值的一对武将组合的军队进行二对二比武,拥有更高默契值的一对武将组合获胜,表示两军交战,拥有获胜武将组合的一方获胜。获胜,表示两军交战,拥有获胜武将组合的一方获胜。已知计算机
10、一方选择武将的原则是尽量破坏对手下一步已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合,它采取的具体策略如下:任何时刻,将形成的最强组合,它采取的具体策略如下:任何时刻,轮到计算机挑选时,它会尝试将对手军队中的每个武将与轮到计算机挑选时,它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对,找出所有配对中默契值当前每个自由武将进行一一配对,找出所有配对中默契值最高的那对武将组合,并将该组合中的自由武将选入自己最高的那对武将组合,并将该组合中的自由武将选入自己的军队。的军队。15 四月四月 202410二应用举例 下面举例说明计算机的选将策略,例如,游戏中下面举例说明计算
11、机的选将策略,例如,游戏中一共有一共有6 6个武将,他们相互之间的默契值如下表所示个武将,他们相互之间的默契值如下表所示 双方选将过程如下所示:双方选将过程如下所示:15 四月四月 202411武将相互之间的默契值:武将相互之间的默契值:双方选将过程入图所示:双方选将过程入图所示:二应用举例 小涵想知道,如果计算机在一局游戏中始终坚持小涵想知道,如果计算机在一局游戏中始终坚持上面这个策略,那么自己有没有可能必胜?如果有,上面这个策略,那么自己有没有可能必胜?如果有,在所有可能的胜利结局中,自己那对用于比武的武将在所有可能的胜利结局中,自己那对用于比武的武将组合的默契值最大是多少?组合的默契值最
12、大是多少?假设整个游戏过程中,对战双方任何时候均能看假设整个游戏过程中,对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化到自由武将队中的武将和对方军队的武将。为了简化问题,保证对于不同的武将组合,其默契值均不相同。问题,保证对于不同的武将组合,其默契值均不相同。15 四月四月 202412二应用举例【算法分析算法分析】由于计算机的贪心策略,每一个武将不可能与和由于计算机的贪心策略,每一个武将不可能与和他默契度最大的武将合作,但要与和他默契度次大的他默契度最大的武将合作,但要与和他默契度次大的武将合作,变得非常容易,小涵只需要经过两次挑选。武将合作,变得非常容易,小涵只需要经
13、过两次挑选。只要小涵选出默契度次大值中最大的那对武将,只要小涵选出默契度次大值中最大的那对武将,那么他将稳操胜券。那么他将稳操胜券。15 四月四月 202413二应用举例15 四月四月 202414123456152816292722332013832264331151261654323332二应用举例15 四月四月 20241512345678111111170211118013111501416011511161171818765432二应用举例15 四月四月 20241612345678111111170211118013111114160501511161171818765432二应用
14、举例【算法分析算法分析】将所有边按从大到小排序,检查每条边的两个顶将所有边按从大到小排序,检查每条边的两个顶点是否已出现过,有三种情况:点是否已出现过,有三种情况:(1 1)两个顶点都没有出现过,说明两个武将都是)两个顶点都没有出现过,说明两个武将都是自由的,不能同时取到,放弃该边;自由的,不能同时取到,放弃该边;(2 2)有一个顶点出现过,说明这个武将前面可以)有一个顶点出现过,说明这个武将前面可以被小涵先取到,现在可以取另一个顶点,该边即为最被小涵先取到,现在可以取另一个顶点,该边即为最大值;大值;(3 3)两个顶点都出现过,说明这两个武将前面都)两个顶点都出现过,说明这两个武将前面都可以
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 普及 讲座 基于 贪心 算法 应用 举例
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。