贪心算法的应用.doc

贪心算法的应用.doc

ID:48833267

大小:82.51 KB

页数:15页

时间:2020-01-31

贪心算法的应用.doc_第1页
贪心算法的应用.doc_第2页
贪心算法的应用.doc_第3页
贪心算法的应用.doc_第4页
贪心算法的应用.doc_第5页
资源描述:

《贪心算法的应用.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。我们看看下面的例子例1均分纸牌(NOIP2002tg)[问题描述] 有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为1堆上取的

2、纸牌,只能移到编号为2的堆上;在编号为N的堆上取的纸牌,只能移到编号为N-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如N=4,4堆纸牌数分别为:  ① 9 ② 8 ③ 17 ④ 6移动3次可达到目的:  从③取4张牌放到④(981310)->从③取3张牌放到②(9111010)->从②取1张牌放到①(10101010)。[输入]:键盘输入文件名。文件格式:N(N堆纸牌,1<=N<=100)  A1A2…An(N堆纸牌,每堆纸牌初始数,l<=Ai

3、<=10000)[输出]:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。[输入输出样例]a.in: 4 98176屏慕显示:3算法分析:设a[i]为第i堆纸牌的张数(0<=i<=n),v为均分后每堆纸牌的张数,s为最小移到次数。我们用贪心法,按照从左到右的顺序移动纸牌。如第i堆(0v,则将a[i]-v张纸牌从第I堆移动到第I+1堆;(2)   若a[i]

4、方便,我们把这两种情况统一看作是将a[I]-v张牌从第I堆移动到第I+1堆;移动后有:a[I]:=v;a[I+1]:=a[I+1]+a[I]-v;在从第i+1堆中取出纸牌补充第i堆的过程中,可能会出现第i+1堆的纸牌数小于零(a[i+1]+a[i]-v<0)的情况。如n=3,三堆纸牌数为(1,2,27)这时v=10,为了使第一堆数为10,要从第二堆移9张纸牌到第一堆,而第二堆只有2张纸牌可移,这是不是意味着刚才使用的贪心法是错误的呢?我们继续按规则分析移牌过程,从第二堆移出9张到第一堆后,第一堆有10张纸牌,第二堆剩下-7张纸

5、牌,再从第三堆移动17张到第二堆,刚好三堆纸牌数都是10,最后结果是对的,从第二堆移出的牌都可以从第三堆得到。我们在移动过程中,只是改变了移动的顺序,而移动的次数不变,因此此题使用贪心法是可行的。源程序:vari,n,s:integer;v:longint; a:array[1..100]oflongint; f:text;fil:string;begin readln(fil);assign(f,fil);reset(f); readln(f,n);v:=0; fori:=1tondobegin   read(f,a[i])

6、;inc(v,a[i]); end; v:=vdivn;{每堆牌的平均数} fori:=1ton-1doifa[i]<>vthen{贪心选择}begin     inc(s);{移牌步数计数}     a[i+1]:=a[i+1]+a[i]-v;{使第i堆牌数为v}   end;{then} writeln(s);end.利用贪心算法解题,需要解决两个问题:一是问题是否适合用贪心法求解。我们看一个找币的例子,如果一个货币系统有3种币值,面值分别为一角、五分和一分,求最小找币数时,可以用贪心法求解;如果将这三种币值改为一角一分、

7、五分和一分,就不能使用贪心法求解。用贪心法解题很方便,但它的适用范围很小,判断一个问题是否适合用贪心法求解,目前还没有一个通用的方法,在信息学竞赛中,需要凭个人的经验来判断何时该使用贪心算法。二是确定了可以用贪心算法之后,如何选择一个贪心标准,才能保证得到问题的最优解。在选择贪心标准时,我们要对所选的贪心标准进行验证才能使用,不要被表面上看似正确的贪心标准所迷惑,如下面的列子。例2(NOIP1998tg)设有n个正整数,将他们连接成一排,组成一个最大的多位整数。例如:n=3时,3个整数13,312,343,连成的最大整数为:3

8、4331213又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613输入:NN个数输出:连接成的多位数算法分析:此题很容易想到使用贪心法,在考试时有很多同学把整数按从大到小的顺序连接起来,测试题目的例子也都符合,但最后测试的结果却不全对。按这种贪心标准,

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。