第6章 贪心算法

《第6章 贪心算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章贪心算法若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为贪心法。下面我们看一些简单例题。【例1】在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。【算法分析】要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:读入N,M,矩阵数据；Total=0;for(intl=1;l<=N;++l){//对N行进行选择选择第I行最大的数,记为K；Total+=K；}输出最大总和Total；从上例中我

2、们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。特别注意的是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。下面我们看看另一个问题。【例2】部分背包问题给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编

3、程确定一个装货方案，使得装入卡车中的所有物品总价值最大。【算法分析】因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。因此我们非常容易设计出如下算法：问题初始化；//读入数据按Vi从大到小将商品排序；i=1;do{if(m==0)break;//如果卡车满载则跳出循环m=m-w[i];if(m>=0)//将第i种商品全部装入卡车else将(m+w[i])重量的物品i装入卡车;i=i+1;//选择下一

4、种商品}while(m>0&&i<=n);在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。因此，利用贪心策略解题，需要解决两个问题：首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：①可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。②原问题的最优解包含子问题的最优解，即问题具

5、有最优子结构的性质。在背包问题中，第一次选择单位重量价值最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。③其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。下面来看看0-1背包问题。给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动

6、物总价值最大。【分析】对于n种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。即确定一组x1，x2，…，xn，xi∈{0,1}f(x)=max(∑xi*vi)其中，∑(xi*wi)≦w从直观上来看，我们可以按照上例一样选择那些价值大，而重量轻的动物。也就是可以按价值质量比（vi/wi）的大小来进行选择。可以看出，每做一次选择，都是从剩下的动物中选择那些vi/wi最大的，这种局部最优的选择是否能满足全局最优呢？我们来看看一个简单的例子：设n=3，卡车最大载重量是100，三种动物a、b、c的重量分别是40，50，70，其对

7、应的总价值分别是80、100、150。情况a：按照上述思路，三种动物的vi/wi分别为2,2,2.14。显然，我们首先选择动物c，得到价值150，然后任意选择a或b，由于卡车最大载重为100，因此卡车不能装载其他动物。情况b：不按上述约束条件，直接选择a和b。可以得到价值80+100=180，卡车装载的重量为40+50=90。没有超过卡车的实际载重，因此也是一种可行解，显然，这种解比上一种解要优化。问题出现在什么地方呢？我们看看图23从图23中明显可以看出，情况a，卡车的空载率比情况b高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率