《算法笔记》总结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;   //左端点从大到小排序 
	else
		return 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;
}

测试如下：

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