



下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、贪心算法经典例题 在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。我们看看下面的例子 例1 均分纸牌(NOIP2002tg)问题描述有 N 堆纸牌,编号分别为 1,2,, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号
2、为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为:98176移动3次可达到目的:从 取 4 张牌放到 (9 8 13 10) -> 从 取 3 张牌放到 (9 11 10 10)-> 从 取 1 张牌放到(10 10 10 10)。输 入:键盘输入文件名。文件格式:N(N 堆纸牌,1 <= N <= 100)A1 A2 An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000)
3、输 出:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。输入输出样例a.in:49 8 17 6屏慕显示:3 算法分析:设ai为第i堆纸牌的张数(0<=i<=n),v为均分后每堆纸牌的张数,s为最小移到次数。我们用贪心法,按照从左到右的顺序移动纸牌。如第i堆(0<i<n)的纸牌数ai不等于平均值,则移动一次(即s加1),分两种情况移动:(1) 若ai>v,则将ai-v张纸牌从第I堆移动到第I+1堆;(2) 若ai<v,则将v -ai张纸牌从第I+1堆移动到第I堆;为了设计
4、的方便,我们把这两种情况统一看作是将aI-v张牌从第I堆移动到第I+1堆;移动后有:aI:=v;aI+1:=aI+1+aI-v;在从第i+1堆中取出纸牌补充第i堆的过程中,可能会出现第i+1堆的纸牌数小于零(ai+1+ai-v<0 )的情况。如n=3,三堆纸牌数为(1,2,27)这时v=10,为了使第一堆数为10,要从第二堆移9张纸牌到第一堆,而第二堆只有2张纸牌可移,这是不是意味着刚才使用的贪心法是错误的呢?我们继续按规则分析移牌过程,从第二堆移出9张到第一堆后,第一堆有10张纸牌,第二堆剩下-7张纸牌,再从第三堆移动17张到第二堆,刚好三堆纸牌数都是10,最后结果是对的,从第二堆移出
5、的牌都可以从第三堆得到。我们在移动过程中,只是改变了移动的顺序,而移动的次数不变,因此此题使用贪心法是可行的。源程序:vari,n,s:integer;v:longint; a:array1.100of longint; f:text;fil:string;begin readln(fil);assign(f,fil);reset(f); readln(f,n);v:=0; for i:=1 to n do begin read(f,ai); inc(v,ai); end; v:=v di
6、v n; 每堆牌的平均数 for i:=1 to n-1 doif ai<>v then 贪心选择begin inc(s);移牌步数计数 ai+1:=ai+1+ai-v;使第i堆牌数为v end;then writeln(s);end. 利用贪心算法解题,需要解决两个问题:一是问题是否适合用贪心法求解。我们看一个找币的例子,如果一个货币系统有3种币值,面值分别为一角、五分和一分,求最小找币数时,可以
7、用贪心法求解;如果将这三种币值改为一角一分、五分和一分,就不能使用贪心法求解。用贪心法解题很方便,但它的适用范围很小,判断一个问题是否适合用贪心法求解,目前还没有一个通用的方法,在信息学竞赛中,需要凭个人的经验来判断何时该使用贪心算法。二是确定了可以用贪心算法之后,如何选择一个贪心标准,才能保证得到问题的最优解。在选择贪心标准时,我们要对所选的贪心标准进行验证才能使用,不要被表面上看似正确的贪心标准所迷惑,如下面的列子。 例2 (NOIP1998tg)设有n个正整数,将他们连接成一排,组成一个最大的多位整数。例如:n=3时,3个整数13,312,343,连成的最大整数为:
8、34331213又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613输入:NN个数输出:连接成的多位数 算法分析:此题很容易想到使用贪心法,在考试时有很多同学把整数按从大到小的顺序连接起来,测试题目的例子也都符合,但最后测试的结果却不全对。按这种贪心标准,我们很容易找到反例:12,121 应该组成12121而非12112,那么是不是相互包含的时候就从小到大呢?也不一定,如:12,123 就是12312而非12123,这样情况就有很多种了。是不是此题不能用贪心法呢?其实此题是可以用贪心法来求解,只是刚才的贪心标准不对,正确的贪心标准是:先把整数化成字符串,然后再
9、比较a+b和b+a,如果a+b>b+a,就把a排在b的前面,反之则把a排在b的后面。源程序:var s:array1.20 of string; t:string;i,j,k,n:longint;begin readln(n); for i:=1 to n do begin read(k); str(k,si); end; for i:=1 to n-1 do for j:=i+1 to n do &
10、#160; if si+sj<sj+si then begin交换 t:=si; si:=sj; sj:=t; end; for i:=1 to n do write(si);end. 贪心算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选择,也不依赖于子问题的解,因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。练习题-删数问题· 键盘输入一个高精度的正整数N,去掉其中任意M个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和M寻找一种方案使得
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 仓储物流顾问合同范本
- 宠物智能陪伴机器人创新创业项目商业计划书
- 仓库车间租凭合同范本
- 农商产品收购合同范本
- 农场肉类出售合同范本
- 脑电信号在神经科学研究中的应用企业制定与实施新质生产力项目商业计划书
- 作废合同代签协议范本
- 保健食品代销合同范本
- 全部劳务外包合同范本
- 兄弟间车库转让协议书
- 深圳2025中考英语真题及答案
- 八上语文第9课《天上有颗南仁东星》课件
- 齿轮制造工艺技术规范及设备使用
- 全科医学进修汇报
- 六年级下学期英语期末考试质量分析
- 三基培训及知识课件
- 2025年中级经济师资格考试(知识产权专业知识和实务)历年参考题库含答案详解(5套)
- 企业章程标准版范本
- 2025年cocos lua面试题及答案
- 新闻出版行业中层后备干部培训班学习心得体会
- 同业客户管理办法
评论
0/150
提交评论