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

(也叫贪心算法、登山法)我们来看一个找硬币的例子:例1:假设有四种硬币,它们的面值分别为二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。(要求:所拿出的硬币个数是最少。)这里,我们使用了这样的找硬币算法:首先选出一个面值不超过六角三分的最大硬币,即二角五分;然后从六角三分中减去二角五分,剩下三角八分;再选出一个面值不超过三角八分的最大硬币,即又一个二角五分,如此一直做下去。总共用六枚硬币,事实说明这是最好的结果。这个找硬币的方法实际上就是贪婪算法。顾名思义,贪婪算法总是以当前情况为基础,而不考虑全部各种可能的情况,作出在当前状态看来是最好的选择。也就是说贪婪算法并不从整体最优上加以考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,我们希望贪婪算法得到的最终结果也是整体最优的。上面所说的找硬币算法得到的结果就是一个整体最优解。但贪婪算法并不是对所有问题都能得到整体最优解。、5克和1克,待称的物体是15克。(所用砝码个数最少)用贪婪算法应先选一个11克的,然后选四个1克的,共用五个砝码。但这不是最优结果,实际只要用三个5克的砝码就够了。所以贪婪算法并不能保证得到的总是最优结果,但对于一些除了“穷举”方法外没有有效算法的问题,用贪婪算法往往能很快地得出较好的结果,如果此较好结果与最优结果相差不是很多的话,此方法还是很实用的。贪心方法适合的问题:有n个输入,而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成,而把满足约束条件的子集称为该问题的可行解。显然,可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解,称为最优解。贪心方法是求解这一类需求取最优解的问题的一个直接有效的方法。贪心方法是一种分级处理方法,首先根据题意,选取一种量度标准。然后按这种量度标准对这n个输入排序,并按序一次输入一个量。如果这个输入量的加入,不满足约束条件,则不把此输入加到这部分解中。【例2】数列极差问题在黑板上写了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=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显然此问题适合用贪婪策略,不过在求最大值时,要先选择较小的数操作。反过来求最小值时,要先选择较大的数操作。这是一道两次运用贪心策略解决的问题。上节下节