蓝桥杯——专题：贪心法（2017.3.4）

一、0-1背包问题

       装船问题

        某船最大载重量为m吨，现有n件货物供选择装船，每件货物的重量和价值不同。那么从这n件货物中挑选若干件上船，在满足货物总重量<=m的前提下，如何装船才能使运走的货物的总价值最大？

【分析】从价重比（价格/重量）入手，计算每件货物的价重比后，按价重比从大到小排序，在不超重的情况下从价重比最大的货物开始装船。贪心策略正体现在这一点。

源代码：

#include <stdio.h>#define maxn 100struct goods{	double w;             //货物重量	double p;             //货物价值	double pw;            //货物价重比}g[maxn];void sort(struct goods g[],int n)            //按货物价重比由大到小排序 {	int i,j;	struct goods t;	for(i=0;i<n-1;i++)	{		for(j=0;j<n-1-i;j++)		{			if(g[j].pw<g[j+1].pw)			{				t=g[j];				g[j]=g[j+1];				g[j+1]=t;			}		}	}}int main(){	int i,j,n,m;	double sumw,sump;                       //装上船的货物总重量和总价值 	while(scanf("%d %d",&n,&m)!=EOF)	{		for(i=0;i<n;i++)		{			scanf("%lf %lf",&g[i].p,&g[i].w);			g[i].pw=(g[i].p)/(g[i].w);		}		sort(g,n);		sumw=0,sump=0;		j=0;		while((sumw+g[j].w)<=m && j<n)   //贪心策略-在不超重的前提下，按价重比从大到小装货 		{			sumw+=g[j].w;			sump+=g[j].p;			j++;		}		PRintf("total weight=%.2lf/n",sumw);		printf("total value=%.2lf/n",sump);		printf("max p/w=%.2lf/n",sump/sumw);	}	return 0;} 程序截图：
二、事件序列问题
【分析】为叙述方便，下面用Begin[i]表示事件i的发生时刻，用End[i]表示事件i的结束时刻。原题的要求其实就是找到一个最长的序列a1<a2<...<an，满足
        Begin[a1]<End[a1]<=Begin[a2]<=End[a2]<=...<=Begin[an]<End[an]，
        这个序列在时间上不重叠。
        以上结论说明，为了得到当前情况下最优的一个结果，可以在当前可选的事件中选取编号最小的那个进入序列，即选取最早结束的那个事件进入序列，这就是“贪心”策略。如果从一开始就用这一贪心策略，最终可以得到题目所要求的最长的时间序列。
源代码：
#include <stdio.h>const int N=12;                   //事件总数目=12 void output(int Select[])         //输出事件序列  {	int i; 	printf("{0");	for(i=1;i<N;i++)	{		if(Select[i]==1)			printf(",%d",i);	} 	printf("}/n");} int main(){	int Begin[N]={1,3,0,3,2,5,6,4,10,8,15,15};          //各事件开始时刻	int End[N]={3,4,7,8,9,10,12,14,15,18,19,20};        //各事件结束时刻 	int Select[N]={0};                                  //选取事件标记（初始状态均为0）	int i=0;                                            //当前情况下最早结束的事件	int Timestart=0;                                    //当前情况下可选事件的最早开始时刻	while(i++<N)	{		if(Begin[i]>=Timestart)                         //如果满足时间不重叠的条件		{			Select[i]=1;                                //选取事件i			Timestart=End[i];                           //以后的事件应不早于时刻End[i]开始 		} 	}	output(Select);                                     //输出事件序列（即计算结果） 	return 0;} 程序截图：
三、硬币问题
        某国家的硬币体系包含N种面值（其中一定有面值为1的），现有一种商品价格为P，请问最少用多少枚硬币可以正好买下？
        输入N、P及N种面值（保证输入的面值递增有序，且满足1<=N<=7，N种面值的取值是{1,2,5,10,20,50,100}的子集），输出需要的最少硬币数。
【分析】最少硬币->按面值由高到低选硬币，每次P减去选择的硬币面值，直到P=0结束。
源代码：
#include <stdio.h>#define maxn 20void fun(int a[],int N,int P){	int i;	int count=0;	for(i=N-1;i>=0;i--)	{		if(P==0)			break;		while(P-a[i]>=0)               //这里写while意在每种面值的硬币可以重复选取		{			P-=a[i];			count++;		}	} 	printf("count=%d/n",count);}int main(){	int i,a[maxn];	int N,P;	while(scanf("%d",&N)!=EOF)	{		for(i=0;i<N;i++)               //保证面值递增有序，且一定有面值为1的 			scanf("%d",&a[i]);		scanf("%d",&P);		fun(a,N,P);	}	return 0;}程序截图：
拓展：如果面值是任意的，比如N=4 4种面值分别为{1,5,8,10}，P=13，那么count=2而不是4，贪心法在这种情景下就失效了。
        贪心法在某些问题情境中并不能得到最优解，需要结合动态规划的方法完成。