贪心算法

1找零钱问题顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。4.4贪心算法2最优装载有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。3贪心算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。41.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。52.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。6【例】数列极差问题在黑板上写了n个正整数排成的一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为m=max-min。7问题分析对三个具体的数据3，5，7讨论可能有以下三种结果：（3*5+1）*7+1=113、（3*7+1）*5+1=111、（5*7+1）*3+1=109由此可见，先运算小数据得到的是最大值，先运算大数据得到的是最小值。8证明此题用贪心策略求解的合理性,不妨假设：ab=a+k1c=a+k1+k2，k1,k20，则有以下几种组合计算结果：1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+12)(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+13)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1显然此问题适合用贪婪策略,不过在求最大值时，要先选择较小的数操作。反过来求最小值时，要先选择较大的数操作。这是一道两次运用贪心策略解决的问题。9算法设计1）由以上分析，大家可以发现这个问题的解决方法和哈夫曼树的构造过程相似，不断从现有的数据中，选取最大和最小的两个数，计算后的结果继续参与运算，直到剩余一个数算法结束。2)选取最大和最小的两个数较高效的算法是用二分法完成，这里仅仅用简单的逐个比较的方法来求解。注意到由于找到的两个数将不再参与其后的运算，其中一个自然地是用它们的计算结果代替，另一个我们用当前的最后一个数据覆盖即可。所以不但要选取最大和最小，还必须记录它们的位置，以便将其覆盖。3）求max、min的过程必须独立，也就是说求max和min都必须从原始数据开始,否则不能找到真正的max和min。10数据结构设计1)必须用两个数组同时存储初始数据。2)求最大和最小的两个数的函数至少要返回两个数据，为方便起见我们用全局变量实现。ints1,s2;main（）{intj,n,a[100],b[100],max,min;print(“Howmangdata?”);input(n);print(“inputthesedata”);for(j=1;j=n;j=j+1){input(a[j]);b[j]=a[j];}min=calculatemin(a,n);max=calculatemax(b,n);print(“max-min=”,max-min)}calculatemin(inta[],intn){while(n2){max2(a,n);a[s1]=a[s1]*a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]*a[2]+1);}max2(inta[],intn){intj;if(a[1]=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for(j=3;j=n;j++){if(a[j]a[s1]){s2=s1;s1=j;}elseif(a[j]a[s2])s2=j;}}calculatemax(inta[],intn){while(n2){min2(a,n);a[s1]=a[s1]*a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]*a[2]+1);}min2(inta[],intn){intj;if(a[1]=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for(j=3;j=n;j++){if(a[j]a[s1]){s2=s1;s1=j;}elseif(a[j]a[s2])s2=j;}}13算法分析算法中的主要操作就是比较查找和计算，它们都是线性的，因此算法的时间复杂度为O(n)。由于计算最大结果和计算最小结果需要独立进行,所以算法的空间复杂度为O(2n)。21【例】设计一个算法，把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为1的形式。如：7/8=1/2+1/3+1/24。22问题分析基本思想是，逐步选择分数所包含的最大埃及分数，这些埃及分数之和就是问题的一个解。过程如下：1)找最小的n（也就是最大的埃及分数），使分数f1/n；2)输出1/n；3)计算f=f-1/n；4)若此时的f是埃及分数，输出f,算法结束,否则返回1）。23数学模型记真分数F=A/B；对B/A进行整除运算,商为D,余数为0＜K＜A，它们之间的关系如下：B=A*D+K，B/A=D+K/A＜D+1，A/B＞1/(D+1)，记C=D+1。这样我们就找到了分数F所包含的“最大的”埃及分数就是1/C。进一步计算：A/B-1/C=（A*C-B）/B*C也就是说继续要解决的是有关分子为A=A*C-B,分母为B=B*C的问题。24算法设计算法过程如下：1)设某个真分数的分子为A(≠1），分母为B；2)把B除以A的商的整数部分加1后的值作为埃及分数的一个分母C;3)输出1/C；4)将A乘以C减去B作为新的A；5)将B乘以C作为新的B；6)如果A大于1且能整除B,则最后一个分母为B/A；7)如果A＝1,则最后一个分母为B;否则转步骤(2).算法main（）{inta,b,c;print(“inputelement”);input(a);print(“inputdenominator”);input(b);if(a=b)print(“inputerror”);elseif(a=1orbmoda=0)print(a,/,b,=1,/,b/a);elsewhile(a1){c=b\a+1a=a*c-b:b=b*cprint(1/,c);if(bmoda=0){print(+1/;b/a);a=1;}elseprint(+);}}26【例】取数游戏有2个人轮流取2n个数中的n个数，取数之和大者为胜。请编写算法，让先取数者胜，模拟取数过程。27问题分析这个游戏一般假设取数者只能看到2n个数中两边的数,用贪婪策略每次两人都取两边的数中较大的一个数,先取者胜.以A先取为例：eg：2,8,9,6,1,7,10,4,3,15。eg：2,8,9,6,1,7,10,4,15,3。28其实，若我们只能看到两边的数据，则此题无论先取还是后取都无必胜的策略。这时一般的策略是用近似贪婪算法。但若取数者能看到全部2n个数，则此问题可有一些简单的方法，确是一个先取者必胜的策略。数学模型建立：N个数排成一行，我们给这N个数从左到右编号，依次为1，2，…，N，因为N为偶数，又因为是我们先取数，计算机后取数，所以一开始我们既可以取到一个奇编号的数（最左边编号为1的数）又可以取到一个偶编号的数（最右边编号为N的数）。如果我们第一次取奇编号（编号为1）的数，则接着计算机只能取到偶编号（编号为2或N）的数；如果我们第一次取偶编号（编号为N）的数，则接着计算机只能取到奇编号（编号为1或N-1）的数；即无论我们第一次是取奇编号的数还是取偶编号的数，接着计算机只能取到另一种编号（偶编号或奇编号）的数。30这是对第一个回合的分析，显然对以后整个取数过程都适用。也就是说，我们能够控制让计算机自始自终只取一种编号的数。这样，我们只要比较奇编号数之和与偶编号数之和谁大，以决定最开始我们是取奇编号数还是偶编号数即可。（如果奇编号数之和与偶编号数之和同样大，我们第一次可以任意取数，因为当两者所取数和相同时，先取者为胜。算法设计：有了以上建立的高效数学模型，算法就很简单了，算法只需要分别计算一组数的奇数位和偶数位的数据之和，然后先取数者就可以确定必胜的取数方式了。以下面一排数为例：12310567894奇编号数之和为25（=1+3+5+7+9），小于偶编号数之和为30（=2+10+6+8+4）。我们第一次取4，以后，计算机取哪边的数我们就取哪边的数（如果计算机取1，我们就取2；如果计算机取9，我们就取8）。这样可以保证我们自始自终取到偶编号的数，而计算机自始自终取到奇编号的数。32活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。33一个实例例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212f[i]456789101112131434贪心算法描述intgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;intj=1;intcount=1;for(inti=2;i=n;i++){if(s[i]=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列35复杂性分析由于输入的活动以其完成时间的非减序排列，所以算法每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。