第四章(贪心、动态).ppt

贪婪法又叫登山法,它的根本思想是逐步到达山顶,即逐步获得最优解。贪婪算法没有固定的算法框架,算法设计的关键是贪婪策略的选择。一定要注意,选择的贪婪策略要具有无后向性。某状态以后的过程和不会影响以前的状态,只与当前状态或以前的状态有关,称这种特性为无后效性。【例1】数列极差问题在黑板上写了N个正整数作成的一个数列,进行如下操作:每一次擦去其中的两个数a和b,然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中,最大的记作max,最小的记作min,则该数列的极差定义为M=max-min。。对三个具体的数据3,5,7讨论,可能有以下三种结果:(3*5+1)*7+1=113、(3*7+1)*5+1=111、(5*7+1)*3+1=109由此可见,先运算小数据得到的是最大值,先运算大数据得到的是最小值。下面再以三个数为例证明此题用贪心策略求解的合理性,不妨假设:a<b<c,则b=a+k1;c=a+k1+k2,k1,k2>0,则有以下几种组合计算结果: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显然此问题适合用贪婪策略,不过在求最大值时,要先选择较小的数操作。反过来求最小值时,要先选择较大的数操作。这是一道需两次运用贪心策略解决的问题。算法设计1)由以上分析,大家可以发现这个问题的解决方法和哈夫曼树的构造过程相似,不断从现有的数据中,选取最大和最小的两个数,计算后的结果继续参与运算,直到剩余一个数算法结束。2)选取最大和最小的两个数较高效的算法是用二分法完成,这里仅仅用简单的逐个比较的方法来求解。注意到由于找到的两个数将不再参与其后的运算,其中一个自然地是用它们的计算结果代替,另一个我们用当前的最后一个数据覆盖即可。所以不但要选取最大和最小,还必须记录它们的位置,以便将其覆盖。3)求max、min的过程必须独立,也就是说求max和min都必须从原始数据开始,否则不能找到真正的max和min。数据结构设计1)由设计2)、3)知,必须用两个数组同时存储初始数据。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){intj;while(n>2){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){intj;while(n>2){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;}算法分析算法中的主要操作就是比较查找和计算,它们都是线性的,因此算法的时间复杂度为O(n)。由于计算最大结果和计算最小结果需要独立进行,所以算法的空间复杂度为O(2n)。贪婪策略不仅仅可以应用于最优化问题中,有时在解决构造类问题时,用这种策略可以尽快地构造出一组解,如下面的例子:【例4】币种统计问题【例5】