简单的贪心算法ppt.ppt
《简单的贪心算法ppt.ppt》由会员分享,可在线阅读,更多相关《简单的贪心算法ppt.ppt(18页珍藏版)》请在咨信网上搜索。
1、贪心算法详解与应用举例贪心算法详解与应用举例班级:软件班级:软件12-112-1组长:孟洁组长:孟洁组员:王明桃组员:王明桃 赵强赵强5/13/20241详解:详解:算法思想算法思想算法过程算法过程算法分析算法分析应用举例:应用举例:常见应用常见应用5/13/20242算法思想算法思想找钱的方法找钱的方法:25+25+10+5+1+1我们我们有种直觉的倾向有种直觉的倾向:在找零钱时,直觉告诉我们使用面值大的硬币,剩余的金额就越少。假设提供了数目假设提供了数目不限的面值为不限的面值为2 52 5美分、美分、1 01 0美分、美分、5 5美分、及美分、及1 1美分美分的硬币。的硬币。假设一个小假设
2、一个小孩买了孩买了3333美分的美分的糖果(需要找给糖果(需要找给小孩小孩6767美分)。美分)。引例引例找零钱找零钱5/13/20243算法思想算法思想 在现实生活中,我们在现实生活中,我们经常为下意识的做贪心的经常为下意识的做贪心的选择,例如在购买商品时选择,例如在购买商品时候总是寻求物美价廉的物候总是寻求物美价廉的物品,在质量相同情况下,品,在质量相同情况下,价格低的首选价格低的首选。5/13/20244算法思想算法思想 将问题的求解过程看作是一系列选择将问题的求解过程看作是一系列选择,每每次选择一个输入次选择一个输入,每次选择都是当前状态下的每次选择都是当前状态下的最好选择最好选择(局
3、部最优解局部最优解)。每作一次选择后每作一次选择后,所所求问题会简化为一个规模更小的子问题求问题会简化为一个规模更小的子问题。从而从而通过每一步的最优解逐步达到整体的最优解通过每一步的最优解逐步达到整体的最优解。5/13/20245算法过程算法过程 顾名思义,顾名思义,贪心算法总是贪心算法总是作出在当前看来最作出在当前看来最好的选择好的选择。也就是说贪心算法并不从整体最优考。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的虑,它所作出的选择只是在某种意义上的局部最局部最优选择优选择。找的硬币总数最少找的硬币总数最少使剩余金额最少使剩余金额最少找硬币的时候:找硬币的时候:【标
4、准转化】贪心猜想(贪心策略)原现5/13/20246算法过程算法过程 贪心算法步骤贪心算法步骤 从问题的某一初始解出发;从问题的某一初始解出发;whilewhile能朝给定总目标前进一能朝给定总目标前进一步步dodo求出可行解的一个解元素;求出可行解的一个解元素;由所有解元素组合成问题的一个由所有解元素组合成问题的一个可行解;可行解;真正意义要求解原问题真正意义要求解原问题将原问题变成更小将原问题变成更小子问题的步骤子问题的步骤理解理解5/13/20247算法过程算法过程【贪心算法一般步骤】1 1、设计数据找规律、设计数据找规律2 2、进行贪心猜想、进行贪心猜想3 3、正确性证明(严格证明和一
5、般证明)、正确性证明(严格证明和一般证明)严格证明:数学归纳和反证法严格证明:数学归纳和反证法 一般证明:列举反例一般证明:列举反例4 4、程序实现、程序实现若无法证明,此证明可省5/13/20248算法分析算法分析【适用问题】具备贪心选择贪心选择和最优子结构最优子结构性质的最优化问题【常见应用】背包问题,最小生成树,最短路径,作业调度等等【算法优点】求解速度快,时间复杂性有较低的阶.【算法缺点】需证明是最优解.整体的最优解可通过一系列整体的最优解可通过一系列局部最优解达到局部最优解达到.每次的选择每次的选择可以依赖以前作出的选择可以依赖以前作出的选择,但但不能依赖于后面的选择不能依赖于后面的
6、选择问题的整体最优解问题的整体最优解中包含着它子问题中包含着它子问题的最优解的最优解5/13/20249常见应用常见应用1、活动安排问题、活动安排问题【问题陈述问题陈述】设有设有n个活动个活动E=1,2,n要使用同一资源要使用同一资源,同一时间内同一时间内只允许一个活动使用该资源只允许一个活动使用该资源.设活动设活动i的起止时间区间的起止时间区间si,fi),如果选如果选择了活动择了活动i,则它在时间区间则它在时间区间si,fi)内占用该资源内占用该资源;若若si,fi)与与sJ,fJ)不相交不相交,则称活动则称活动 i 与与 j 是是 相容相容 的的.求解目标是在所给的活动集合求解目标是在所
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 简单 贪心 算法 ppt
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。