《算法笔记》总结No.6——贪心

一.简单贪心

        贪心法是求解一类最优化问题的方法，它总是考虑在当前状态下局部最优(或较优)之后，来使全局的结果达到最优(或较优)的策略。显然，如果采取较优而非最优的策略(最优策略可能不存在或是不易想到)，得到的全局结果也无法是最优的。而要获得最优结果，则要求中间的每步策略都是最优的，因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法，即假设策略不能导致最优解，然后通过一系列推导来得到矛盾，以此证明策略是最优的，最后用数学归纳法保证全局最优。不过对平常使用来说，也许没有时间或不太容易对想到的策略进行严谨的证明(贪心的证明往往比贪本身更难)，因此一般来说，如果在想到某个似乎可行的策略之后，并且自己无法举出反例，那么就勇敢地实现它。

1.组个最小数

给定数字0~9各若干个，可以任意顺序排列这些数字，但必须全部使用，且使目标数字尽可能小（当然0不能做首位）比如输入两个0、两个1、三个5和一个8，得到的最小数字就是100155858。

相信大家一下子就可以看出来策略：先从1~9中选择不为0的最小数输出，然后从0~9输出数字，每个数字输出次数为其剩余个数。

策略正确的证明：

• 首先由于所有数字都必须参与组合，因此最后结果的位数是确定的。 
• 由于最高位不为0，则选一个尽可能小的数作为首位——最高位定理
• 其余位数也应该从小到大输出~

教材上的实在是太抽象了，好像有点错误，这里博主自己写了一种：

#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;int main() {	vector<int> V;for(int i=1;i<=10;i++){int temp=0;cin>>temp;V.push_back(temp);}sort(V.begin(),V.end());  //直接排成升序 int flag=0;  //标记 for(int i=0;i<=9;i++)if(V[i]!=0){int temp=V[i];V[i]=V[0];V[0]=temp;flag=i;//保存第一个不为0的位置 break;	}for(int i=flag+1;i<=9;i++)  //找更小的头，直接从flag下一位开始即可，节省时间~ if(V[i]<V[0]&&V[i]!=0){int temp=V[i];V[i]=V[0];V[0]=temp;}for(int i=0;i<=9;i++)cout<<V[i];
}

逻辑上没什么难度，主要是要想清楚~

2.月饼库存

• 输入：第一行输入N和M：N位月饼的种类数目，M位市场对月饼的需求总量；接下来的两行均要输入N个数：第一行的N个数分别对应当前种类的月饼全部卖出后可以挣多少，而第二行的N个数对应当前月饼的总数量~
• 要求输出：在规定需求量下最高收入

        试想一下你如果作为老板，会怎么去“贪得无厌”？很明显——只需要在有限的需求量中，尽可能多的卖出单价最贵的月饼，岂不是可以收货最多的营业额？如下博主自己写的一种实现，和教材上的也不太一样：

#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;struct mooncake{double num;  //总数 double income;  //总收入 double price;   //单价，需要自己计算 
}; int main() {int N,M;cin>>N>>M;vector<mooncake> V;for(int i=1;i<=N;i++) {mooncake temp;V.push_back(temp);}cout<<"请输入数量："<<endl;for(int i=1;i<=N;i++) {double num=0;cin>>num;V[i-1].num=num;}cout<<"请输入总价："<<endl;for(int i=1;i<=N;i++) {double income=0;cin>>income;V[i-1].income=income;}for(int i=0;i<=N-1;i++) V[i].price=V[i].income/V[i].num; //计算单价//按单价降序排列！保证贵的尽可能多卖for(int i=0;i<=V.size()-1;i++){for(int j=i;j<=V.size()-1;j++)    if(V[j].price>V[i].price)    {mooncake temp;temp=V[j];V[j]=V[i];V[i]=temp;}}for(int i=0;i<=V.size()-1;i++)cout<<"单价第"<<(i+1)<<"高的值为："<<V[i].income<<" "<<V[i].price<<" "<<V[i].num<<endl;for(int i=0;i<=N-1;i++)cout<<V[i].num<<endl; int j=0;  //使用的下标 double count=0;  //总利润 while(M>0)  //当还有需求量时 {double doubt=0;doubt=M-V[j].num; //用M减去当前类型的额总量 if(doubt>=0)//减了以后M还有剩余{M-=V[j].num;//当前种类全部卖出 count+=V[j].income;//直接总价相加 j++;cout<<V[j].num;}else if(doubt<0) //不够减这么多{count+=V[j].price*M;//剩余部分按照单价计算 break; } }cout<<"最高利润值为："<<count<<endl;return 0;
}

        仔细品味上述中的whlie循环：当M还不为0时——即还有需求量，就卖最贵的月饼。按顺序一个一个卖：如果当前需求量足以卖完当前种类的全部数量，则直接累加总价；如果不足以卖完当前的全部，则有多少卖多少，按照单价计算即可~ 

我们拿教材的测试用例测试一下：

• 3 20
• 18 15 10
• 75 72 45

结果为94.50，和标准答案一致~ 

此外这里博主直接把排序写在main函数了，写在独立的函数再调用，对于结构体型的vector好像有点bug，排序不太成功，大家如果知道原因的话可以在评论区写出来~

二.区间贪心

题干如下：

对于这类题目，只需要牢记——优先选择左端点大的区间！

下面来说说为什么要这样做，如上图：不难发现，为了保证尽可能多选，当某个较长的区间包含了较短的区间，我们肯定要先选择最短的区间，这一点很好理解。

        而对于上面这种情况，比如1和2这种重叠的区间，不难发现，如果选了左端点最大的1区间，只会占到9号位，而选了2号区间则会占到8号位——这显然不符合贪心尽可能少花钱（少花区间）的思想，因此要选得尽可能靠左，这样右边空的会更多~如上，我们手算可以看出来最多有4个不相交的。 

教材上的代码： 

#include <cstdio>
#include <algorithm>
using namespace std;const int maxn=110;
struct Inteval{int x,y;  //开区间左右端点 
}I[maxn]; bool cmp(Inteval a,Inteval b)
{if(a.x!=b.x)return a.x>b.x;   //左端点从大到小排序 elsereturn a.y<b.y;   //左端点相同的按右端点从小到大排序 
}int main() {int n;while(scanf("%d",&n,n!=0)){for(int i=0;i<n;i++)scanf("%d%d",&I[i].x,&I[i].y);sort(I,I+n,cmp); //排序区间 int ans=1,lastX=I[0].x;//ans记录总数，lastX记录上一个被选择的区间的左端点 for(int i=1;i<n;i++){if(I[i].y<=lastX)   //如果该区间右端点在lastX左边 {lastX=I[i].x;  //以I[i]作为新选中的区间 ans++;   //不相交的区间个数+1 }	}printf("%d\n",ans);	} return 0;
}

不过博主还是不太喜欢原始数组，下面给一种vector结构体版本：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct section{int x=0;int y=0;//x和y分别为左右端点 
}; int main() {int n=0;vector<section> V;cin>>n;for(int i=1;i<=n;i++) //读入数据 {section temp;int x=0,y=0;cin>>x>>y;if(x>y)   //防止左端点大于右端点 {int temp1=x;x=y;y=temp1;	}else if(x==y) //若左右端点相同 {i-=1;  //则当前输入 不算cout<<"不可以输入相同的左右端点！"<<endl; continue;  //舍弃数据，本次循环作废~ }	temp.x=x;temp.y=y;V.push_back(temp);}//按要求排序区间优先级 for(int i=0;i<=V.size()-1;i++){for(int j=i+1;j<=V.size()-1;j++){if(V[j].x>V[i].x)  //左端点越大越靠前{section temp=V[j];V[j]=V[i];V[i]=temp;}else if(V[j].x==V[i].x&&V[j].y<V[i].y) //左端点相同的话，右端点小的优先 {section temp=V[j];V[j]=V[i];V[i]=temp;} }}cout<<"顺序如下："<<endl; for(int i=0;i<=V.size()-1;i++)cout<<V[i].x<<"~"<<V[i].y<<endl; int count=1,lastX=V[0].x;//count用来统计总数，lastX是上一个符合条件的区间的左端点for(int i=1;i<=V.size()-1;i++)//直接从第二个区间开始 {if(V[i].y<lastX)  //如果当前区间的右端点不和上一个左端点相加，满足题意 {lastX=V[i].x;count++;}		} cout<<count<<endl;return 0;
}

测试如下：

        总的来说，贪心法是用来解决一类最优化问题，并希望由局部最优策略来推得全局最优结果的算法思想。贪心算法适用的问题一定满足最优子结构的性质，即一个问题的最优解可以由他的子问题的最优解有效地构造出来。显然不是所有问题都适合贪心法，但是这并不妨碍贪心算法成为一个简洁、实用、高效的算法~