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

发布于:2024-07-11 ⋅ 阅读:(21) ⋅ 点赞:(0)

一.简单贪心

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

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;
}

测试如下:

 


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