贪心算法的应用

《贪心算法的应用》由会员分享，可在线阅读，更多相关《贪心算法的应用（15页珍藏版）》请在装配图网上搜索。

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

2、为N-1的堆上；其他堆上取的纸牌，可以移到相邻左 边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如N=4, 4堆纸牌数分别为：98176移动3次可达到目的：从取4张牌放到（9 813 10）-从取3张牌放到（9 11 1010）-从取1张牌放到（10 10 10 10）。输入：键盘输入文件名。文件格式：N（N堆纸牌，1 = N = 100）A1 A2 . An （N堆纸牌，每堆纸牌初始数，l= Ai = 10000）输出：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。输入输出样例a.in:49 8 17 6屏慕显示：3算法分析：设ai为第i堆纸牌的

3、张数（0 = i = n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆（0iv，则将ai-v张纸牌从第I堆移动到第I+1堆；（2）若aiv，则将v -ai张纸牌从第I+1堆移动到第I堆；为了设计的方便，我们把这两种情况统一看作是将aI-v张牌从第I堆移动到第I+1堆；移动后有： aI:=v； aI+1:=aI+1+aI-v；在从第i + 1堆中取出纸牌补充第i堆的过程中，可能会出现第i + 1堆的纸牌数小于零（ai + 1+ai-v0 ） 的情况。如n = 3,三堆纸牌数为（1，2, 27）这时v=10，为了使第一堆数为10，要从第二堆移9

4、张纸牌到第一 堆，而第二堆只有2张纸牌可移，这是不是意味着刚才使用的贪心法是错误的呢？我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张纸牌，第二堆剩下-7张纸 牌，再从第三堆移动17张到第二堆，刚好三堆纸牌数都是10，最后结果是对的，从第二堆移出的牌都可 以从第三堆得到。我们在移动过程中，只是改变了移动的顺序，而移动的次数不变，因此此题使用贪心法 是可行的。源程序：vari, n,s:integer;v:longint;a:array1.100of longint;f:text;fil:string;beginreadln(fil);assign(f,fil);reset

5、(f);readln(f,n);v:=0;for i: = 1 to n do beginread(f,ai); inc(v,ai);end;v:=v div n; 每堆牌的平均数for i: = 1 to n-1 doif aiv then 贪心选择begininc(s);移牌步数计数ai+1:=ai + 1+ai-v;使第 i 堆牌数为 vend;thenwriteln(s);end.利用贪心算法解题，需要解决两个问题：一是问题是否适合用贪心法求解。我们看一个找币的例子,如果一个货币系统有3种币值，面值分别为一角、 五分和一分，求最小找币数时，可以用贪心法求解；如果将这三种币值改为一角一分

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

7、246连接成的最大整数为7424613输入：NN个数输出:连接成的多位数算法分析：此题很容易想到使用贪心法，在考试时有很多同学把整数按从大到小的顺序连接起来，测试题 目的例子也都符合，但最后测试的结果却不全对。按这种贪心标准，我们很容易找到反例：12，121应 该组成12121而非12112,那么是不是相互包含的时候就从小到大呢？也不一定，如：12，123就是 12312而非12112,这样情况就有很多种了。是不是此题不能用贪心法呢？其实此题是可以用贪心法来求解，只是刚才的贪心标准不对，正确的贪心标准是：先把整数化成字符串， 然后再比较a+b和b+a，如果a+bb+a，就把a排在b的前面，反之

8、则把a排在b的后面。源程序：vars:array1.20 of string;t:string;i,j,k,n:longint;beginreadln(n);for i: = 1 to n do beginread(k);str(k,si);end;for i: = 1 to n-1 dofor j: = i + 1 to n doif si+sjsj+si thenbegin交换t:=si;si:=sj;sj:=t;end;for i: = 1 to n do write(si); end.贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解， 因此贪心

9、算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应 该是最好的选择之一。贪心算法经典例子(2009.07.15 10:17:04)分类：简单算法&标签：贪心 算法 背包问题it、定义什么是贪心算法呢？所谓贪心算法是指，在对问题求解时，总是做出在当前看来最好 的选择。也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优 解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题都能产 生整体最优解或整体最优解的近似解。贪心算法的基本思路如下：1. 建立数学模型来描述问题。2. 把求解的问题分成若干个子问题。3. 对每个子问题求解

10、，得到每个子问题的局部最优解。4. 把每个子问题的局部最优解合成为原来问题的一个解。实现该算法的过程:从问题的某一初始状态出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；二、例题分析背包问题有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品 A BCDEFG重量 35 306050401025价值 10 403050354030记得当时学算法的时候，就是这个例子，可以说很经典。分析：目标函数：Epi最大约束条件是装入的物品总重量不超过背包容量，即Ewi=M(

11、M=150)(1) 根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？(2) 每次挑选所占重量最小的物品装入是否能得到最优解？(3) 每次选取单位重量价值最大的物品，成为解本题的策略？贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。但是，它 需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着整个问题的最 优解一定由在贪心策略中存在的子问题的最优解得来的。对于本例题中的3种贪心策略，都无法成立，即无法被证明，解释如下：(1) 贪心策略：选取价值最大者。反例：W=30物品：A B C重量：28 12 12价值：30 20 20根据策略，首先选取

12、物品A,接下来就无法再选取了，可是，选取B、C则更好。（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。（3）贪心策略：选取单位重量价值最大的物品。反例：W=30物品：A B C重量：28 20 10价值：28 20 10根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A， 则答案错误。值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它 就是一种高效的算法。比如，求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算 法。均分纸牌有N堆纸牌，编号分别为1，2,，n。每堆上有若干张,但纸牌总数必 为n的倍数.可以在任一堆上取

13、若干张纸牌，然后移动。移牌的规则为：在编号为1上取的纸 牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上; 其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少 的移动次数使每堆上纸牌数都一样多。例如：n=4, 4堆纸牌分别为：98176 移动三次可以达到目的：从取4张牌放到 再从区3张放到然后从去1张放到。输入输出样例：49 8 17 6屏幕显示：3算法分析：设ai为第I堆纸牌的张数（0=Iv,则将ai-v张从第I堆移动到第I+1堆；2. 若aiv,则将v-ai张从第I+1堆移动到第I堆。为了设计的方便，我们把这两种情况统一看作是将

14、ai-v从第I堆移动到第I+1堆， 移动后有 ai=v; aI+1=aI+1+ai-v.在从第I+1堆取出纸牌补充第I堆的过程中可能回出现第I+1堆的纸牌小于零的情况。如n=3，三堆指派数为1 2 27，这时v=10，为了使第一堆为10，要从第二堆移9张 到第一堆，而第二堆只有2张可以移，这是不是意味着刚才使用贪心法是错误的呢？我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张，第二 堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的，我 们在移动过程中，只是改变了移动的顺序，而移动次数不便，因此此题使用贪心法可行的。Java源程序：publi

15、c class Greedy public static void main(String args) int n = 0, avg =0, s = 0;Scanner scanner = new Scanner(System.in);ArrayList array = new ArrayList();System.out.println(Please input the number of heaps:);n = scanner.nextInt();System.out.println(Please input heap number:);for (int i = 0; i n; i+) a

16、rray.add(scanner.nextInt();for(int i = 0; i array.size(); i +)avg += array.get(i);avg = avg/array.size();System.out.println(array.size();System.out.println(avg);for(int i = 0; i =b+a，就把a排在b的前面，反之则把a排在 b的后面。java源程序:public static void main(String args)String str = ；ArrayList array = new ArrayList();Sc

17、anner in = new Scanner(System.in);System.out.println(Please input the number of data:);int n = in.nextInt();System.out.println(Please input the data:);while (n 0) array.add(in.next();for(int i = 0; i array.size(); i +)for(int j = i + 1; j array.size(); j +)if(array.get(i) + array.get(j).compareTo(ar

18、ray.get(j) + array.get(i) 0)String temp = array.get(i);array.set(i, array.get(j);array.set(j, temp);for(int i = 0; i array.size(); i +)str += array.get(i);System.out.println(str=:+str);贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不 依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以 同时用几种方法解决，贪心算法应该是最好的选择之一。贪心算法实例：找零钱(

19、Java实现)收藏/*从桌面txt文件里读取零钱数目以及需要找的钱总额然后利用贪心算法求解之后重新生成txt文件力$力“*import java.io.*;public class GreedySelectpublic GreedySelect( String file)throws IOExceptiontrythis.file=file;FileReader reader=new FileReader(file);BufferedReader Breader=new BufferedReader(reader);String s=Breader.readLine();int i,j;cha

20、nge=new Change10;int k=0;while(s!=null)j=0;i=0;String temp=new String9;temp=s.split(s);changek=new Change();while(i6)int num=Integer.parseInt(tempi);if(num=0) j+;changek.coinsi=num;i+;if(j=5) break;double money=Double.parseDouble(tempi)*100;changek.money=(int)money;k+;s=Breader.readLine();client=k-1

21、;Breader.close();catch(IOException e )e.printStackTrace();public void greedySort()/核 心代码，贪心求解double money;double temp=0;for(int i=0;i=0;j-)if(j=5) temp=200;else if(j=4) temp=100;else if(j=3) temp=50;else if(j=2) temp=20;else if(j=1) temp=10;else if(j=0) temp=5;if(money=temp&changei.coinsj0)money-=te

22、mp;changei.needCoinsj+;changei.coinsj-;if(money=temp&changei.coinsj0) j+;if(money!=0) changei.successful=false;else changei.successful=true;public void saveResult()throws lOException/保 存解决方案文件到桌面tryFileWriter fileW=new FileWriter(C:Documents and SettingsAdministrator 桌面 solution.txt);PrintWriter wri

23、ter=new PrintWriter(fileW);for(int i=0;iclient;i+)if(changei.successful)writer.println(顾客+i+需要”+changei.money+找零钱如下：”)；for(int j=0;j0)if(j=0) writer.println(五分: +k);else if(j=1) writer.println( 一角：+k);else if(j=2) writer.println(两角：+k);else if(j=3) writer.println(五角:+k);else if(j=4) writer.println(一

24、兀：+k);else if(j=5) writer.println(一元：+k);elsewriter.println(顾客+i+无法完成);writer.close();catch(IOException e)e.printStackTrace();private int client;private Change change;private String file;private class Changepublic Change()/定义顾客问题类coins=new int6;needCoins=new int6;successful=false;money=0;public int

25、coins;public int needCoins;public int money;public boolean successful;（一）问题描述一辆汽车加满油后可以行驶N千米。旅途中有若十个加油站。指出若要使沿 途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的 加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算 法执行的速度越快越好。（二）问题分析（前提行驶前车里加满油）对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为 ai； i=0， 1， 2，3n1. 始点到

26、终点的距离小于N，则加油次数k=0；2. 始点到终点的距离大于N，A加油站间的距离相等，即a i=aj=L=N，则加油次数最少k=n；B加油站间的距离相等，即a i=aj=LN，则不可能到达终点；C加油站间的距离相等，即a i=aj=LN，则加油次数k=n/N（n%N=0） 或 k=n/N+1（n%N! =0）；D加油站间的距离不相等，即a i! =aj，则加油次数k通过以下算法 求解。（三）算法描述贪心算法的基本思想该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说， 每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可 以得到全局的最优解。贪心算法将问题的求

27、解过程看作是一系列选择，从问题的 某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递 推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断 地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一 个全局得最优解。贪心算法的适用的问题贪心算法适用的问题必须满足两个属性:(1) 贪心性质：整体的最优解可通过一系列局部最优解达到，并且每 次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。(2) 最优子结构：问题的整体最优解包含着它的子问题的最优解。贪心算法的基本步骤(1) 分解：将原问题分解为若干相互独立的阶段。(2) 解决：对于每一个阶段

28、求局部的最优解。(3) 合并：将各个阶段的解合并为原问题的解。问题分析由于汽车是由始向终点方向开的，我们最大的麻烦就是不知道在哪个加油站 加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以 假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油 站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是 一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原 问题的解得到我们原问题的求解。加油站贪心算法设计(C)：includeincludeint add(int b ,int m

29、,int n)( 求一个从m到n的数列的和int sb;for(int i=m;iN) return ERROR; /如果某相邻的两个加油站间的距离大于N， 则不能到达终点if(add(ai, 0, n)N)( 如果这段距离小于匕则不需要加油bi=0;return add(bi,0,n);if(ai=aj&ai=N)( /如果每相邻的两个加油站间的距离都是N,则每个加油站都需要加油 bi = 1;return add(bi,0,n);if(ai=aj&aiN)( /如果每相邻的两个加油站间的距离相等且都小于Nif( add(ai,m,k) N )(bk = 1;m+=k;return add(

30、bi,0,n);if(ai!=aj)( /如果每相邻的两个加油站间的距离不相等且都小于Nif( add(ai,m,k) N )(bk = 1;m+=k;return add(bi,0,n);viod main()(int a;scanf(%d,a);scanf(/n);scanf(/d,&N);Tanxin(a ,0,n);贪心算法正确性证明：贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的 选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质， 我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在 加满油后可行驶的N千米这段路程上

31、任取两个加油站A、B,且A距离始点比B 距离始点近，则若在B加油不能到达终点那么在A加油一定不能到达终点，因为 m+Nn+N,即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米， 所以只要终点不在B、C之间且在C的右边的话，根据贪心选择，为使加油次数 最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足 贪心选择性质。最优子结构性质：当一个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子 结构性质。由于(b1,b2,bn)是这段路程加油次数最少的一个满足贪 心选择性质的最优解，则易知若在第一个加油站加油时，b1=1,则(b2,b3,bn)是从a2到an这段路程上加油次数最少且这段路程 上的加油站个数为(a2,a3,an)的最优解，即每次汽车中剩下的油不 能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始 行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过 程都是相同且独立，也就是说加油次数最少具有最优子结构性质。贪心算法时间复杂度分析由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复 遍历，所以时间复杂度为O(n)。