# **贪心算法** ## 思路 ​ 若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。 那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为**贪心法** **【例1】**在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。 **【算法分析】** ​ 要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法: 读入N, M,矩阵数据； ``` c Total = 0; for (int l= 1; l<= N; ++l) { //对N行进行选择 选择第I行最大的数,记为K； Total +=K； } 输出最大总和Total； ``` ​ 从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。 ​ 特别注意的是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。下面我们看看另一个问题。 **【例2】部分背包问题** ​ 给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。 **【算法分析】** ​ 因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。 ​ 因此我们非常容易设计出如下算法： 问题初始化； //读入数据 按Vi从大到小将商品排序； ``` c++ 　i=1; 　　do 　　{ 　　 if (m==0) break; //如果卡车满载则跳出循环 　　 m=m-w[i]; 　　 if (m>=0) //将第i种商品全部装入卡车 　　 else 将(m+w[i]) 重量的物品i装入卡车; 　　 i=i+1; //选择下一种商品 　　}while (m>0&&i<=n); ``` ​ 在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。 ## 贪心解决的问题 **因此，利用贪心策略解题，需要解决两个问题：** ​ **首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：** ​ **①**可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。 **②**原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位重量价值最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。 ​ **③**其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。 ## 例题讲解 **下面来看看0-1背包问题。** ​ 给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。　　 【分析】对于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，其对应的总价值分别是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 ![image-20201130172725709](https://picreso.oss-cn-beijing.aliyuncs.com/image-20201130172725709.png) ​ 从图23中明显可以看出，情况a，卡车的空载率比情况b高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。 因此，贪心不能简单进行，而需要全面的考虑，最后得到证明。 **【例3】排队打水问题** ​ 有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？ **【算法分析】** ​ 由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤： 1. 将输入的时间按从小到大排序； 2. 将排序后的时间按顺序依次放入每个水龙头的队列中； 3. 统计，输出答案。 **【样例输入】** 4 2 //4人打水，2个水龙头 2 6 4 5 //每个打水时间 ### 实现代码 ``` c++ cin>>n>>r; memset(s,0,sizeof(s)); //初始化 j=0; min=0; for (i=1;i<=n;++i) //用贪心法求解 { j++; if (j==r+1) j=1; s[j]+=a[i]; min+=s[j]; } cout<从③取3张牌放到 ②（9 11 10 10）-> 从②取1张牌放到①（10 10 10 10）。 【输入格式】 ​ N（N 堆纸牌，1 <= N <= 100） ​ A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） 【输出格式】 ​ 所有堆均达到相等时的最少移动次数。 【样例输入】Playcard.in 　 4 　 9 8 17 6 【样例输出】Playcard.out 　 3 【算法分析】 　　如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张数为10,原张数9，8，17，6，变为-1，-2，7，-4，其中没有为0的数，我们从左边出发：要使第1堆的牌数-1变为0，只须将-1张牌移到它的右边（第2堆）-2中；结果是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边（第3堆）中去，各堆牌张数变为0，0，4，-4；要使第3堆变为0，只需将第3堆中的4移到它的右边（第4堆）中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样的。 　　如果张数中本来就有为0的，怎么办呢？如0，-1，-5，6，还是从左算起（从右算起也完全一样），第1堆是0，无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变为0了，可节省1步，余下继续。 ### 实现代码 ``` c++ cin>>n; 　　ave=0;step=0; 　　for (i=1;i<=n;++i) 　　 { 　　　　cin>>a[i]; ave+=a[i]; //读入各堆牌张数，求总张数ave 　　 } 　　ave/=n; //求牌的平均张数ave 　　for (i=1;i<=n;++i) a[i]-=ave; //每堆牌的张数减去平均数 　　i=1;j=n; 　　while (a[i]==0&&i1) --j; //过滤右边的0 　　while (in[j+1] ) { //找到第一个符合条件的 for ( k=j;k导弹i的高度}；l[p]←导弹i的高度)（i≤j≤k）。这样可使得一套系统拦截的导弹数尽可能增多。 　　依次类推，直至分析了n枚导弹的高度为止。此时得出的k便为应配备的最少系统数。 ### 实现代码 ``` c++ 　k=1;l[k]=导弹1的高度; for (i=2;i<=n;++i) { 　　　p=0; 　　　for (j=1;j<=k;++j) if (l[j]>=导弹i的高度) { if (p==0) p=j; 　　　　　　　　　　　　　　　else if (l[j] using namespace std; int n,begin[1001],end[1001]; void init() { cin>>n; for(int i=1;i<=n;i++) cin>>begin[i]>>end[i]; } void qsort(int x,int y) { int i,j,mid,t; i=x;j=y;mid=end[(x+y)/2]; while(i<=j) { while(end[i]mid) --j; if(i<=j) { t=end[j];end[j]=end[i];end[i]=t; t=begin[j];begin[j]=begin[i];begin[i]=t; ++i;j; } } if(x=t) {++ans;t=end[i];}//如果当前活动与之前最后结束的活动不冲突， 就接受当前活动。 cout< using namespace std; int a[10001],b[10001],sum=0,n,m; void qsort(int x,int y) //多关键字快排 { int i,j,mid1,mid2,t; i=x;j=y;mid1=b[(x+y)/2];mid2=a[(x+y)/2]; while(i<=j) { while(b[i]mid1||((b[j]==mid1)&&(a[j]>mid2))) --j; if(i<=j) { t=b[j];b[j]=b[i];b[i]=t; t=a[j];a[j]=a[i];a[i]=t; ++i; --j; } } if(x>n; for(int i=1;i<=n;++i)cin>>a[i]>>b[i]; qsort(1,n); for(int i=1,x=-1;i<=n;++i) //在初始化循环变量的同时，初始化x。 //令x=-1可以使第一个区间与其他区间的操作 相同。 { if (x>=a[i]) continue; //如果当前区间包含标记点，就跳过。 ++sum; x=b[i]; //更新标记点。 } cout<