- 1、本文档共81页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
计算机算法基础(第三章)资料
第三章 贪心方法 3.1 一般方法 1. 问题的一般特征 问题有n个输入,问题的解是由这n个输入的某个子集组成,这个子集必须满足某些事先给定的条件。 约束条件:子集必须满足的条件; 可行解:满足约束条件的子集;可行解可能不唯一; 目标函数:用来衡量可行解优劣的标准,一般以函数的形式给出; 最优解:能够使目标函数取极值(极大或极小)的可行解。 分类:根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同,可分为:线性规划、整数规划、非线性规划、动态规划等。 ——最优化问题求解 贪心方法:一种改进的分级的处理方法,可对满足上述特征的某些问题方便地求解。 例[找零钱] 一个小孩买了价值少于1元的糖,并将1元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为25分、10分、5分及1分的硬币。售货员分步骤组成要找的零钱数,每次加入一个硬币。 选择硬币时所采用的贪心算法如下:每一次选择应使零钱数尽量增大。为确保解法的可行性(即:所给的零钱等于要找的零钱数),所选择的硬币不应使零钱总数超过最终所需的数目。 假设需要找给小孩67分,首先入选的是两枚25分的硬币,第三枚入选的不能是25分的硬币,否则将不可行(零钱总数超过67分),第三枚应选择10分的硬币,然后是5分的,最后加入两个1分的硬币。 贪心算法有种直觉的倾向,在找零钱时,直觉告诉我们应使找出的硬币数目最少(至少是接近最少的数目) 2. 贪心方法的一般策略 问题的一般特征:问题的解是由n个输入的、满足某些事先给定的条件的子集组成。 1)一般方法 根据题意,选取一种度量标准。然后按照这种度量标准对n个输入排序,并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解,则不把此输入加到这部分解中。否则,将当前输入合并到部分解中从而得到包含当前输入的新的部分解。 2)贪心方法 这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法 注: 贪心解 最优解 直接将目标函数作为量度标准也不一定能够得到问题的最优解 3)使用贪心策略求解的关键 选取能够得到问题最优解的量度标准。 3. 贪心方法的抽象化控制描述 procedure GREEDY(A,n) //A(1:n)包含n个输入// solution←Φ //将解向量solution初始化为空// for i←1 to n do x←SELECT(A) //按照度量标准,从A中选择一个输入,其值赋予x 并将之从A中删除// if FEASIBLE(solution,x) then //判定x是否可以包含在解向量中, 即是否能共同构成可行解// solution←UNION(solution,x) //将x和当前的解向量合并成新的解 向量,并修改目标函数// endif repeat return(solution) end GREEDY 3.2 背包问题 1.问题的描述 已知n种物品具有重量(w1,w2,…,wn)和效益值(p1,p2,…,pn) ,及一个可容纳M重量的背包;设当物品i全部或一部分xi放入背包将得到pi xi的效益,这里,0≤ xi ≤1, pi 0。 问题:采用怎样的装包方法才能使装入背包的物品的总效益最大? 分析: ① 装入背包的总重量不能超过M ② 如果所有物品的总重量不超过M,即 ≤M,则把所有的物品都装入背包中将获得最大可能的效益值 ③ 如果物品的总重量超过了M,则将有物品不能(全部)装 入背包中。由于0≤xi≤1,所以可以把
您可能关注的文档
- 计算机病毒原理与防范基础.ppt
- 液压气动_实验指导书概要.doc
- 计算机新技术.ppt
- 计算机病毒的历史.ppt
- 计算机病毒的发展过程.ppt
- 计算机病毒基础知识资料.ppt
- 液压模块三课题8.ppt
- 计算机病毒知多少.ppt
- 计算机的体系结构.ppt
- 计算机病毒virus_4讲.ppt
- 七章货物的保险.pptx
- 三章国际间接投资.pptx
- 人性假设理论.pptx
- 外研高一英语必修三ModuleIntroduction汇总市公开课获奖课件省名师示范课获奖课件.pptx
- 月相成因优质获奖课件.pptx
- 小学二年级语文课件《狐假虎威》省名师优质课赛课获奖课件市赛课一等奖课件.pptx
- 养羊业概况专题知识讲座.pptx
- 微生物的实验室培养市公开课获奖课件省名师示范课获奖课件.pptx
- 人教版六年级下册式与方程整理与复习市公开课获奖课件省名师示范课获奖课件.pptx
- 必威体育精装版高中精品语文教学:第二单元-第7课-诗三首:涉江采芙蓉、-短歌行、归园田居市公开课获奖课件省名师.pptx
最近下载
- 2021上海春考作文题“走进阳光的能力……解析及范文.docx VIP
- 学前儿童美术教育活动指导形成性考核一.docx
- 国庆节新中国成立75周年 全文.pptx
- 冀教版九年级英语上册 (Staying Safe in an Earthquake)Safety 课件.pptx
- 三七中总皂苷提取工艺流程方案论文.pdf
- 2024成都道法中考试题研究备考 真题精练(含答案).doc
- 福建省厦门市2021-2022学年九年级上学期期末考英语试卷.pdf VIP
- 2022-2023学年福建省厦门市九年级上学期期末考英语试卷含详解.docx VIP
- CAD系统变量参数解析(最全最详细).docx
- 市场行为的宝藏系列研究二:抢跑者的脚步声,基于价量互动的选股因子.pdf VIP
文档评论(0)