贪心思想

贪心思想
贪心思想，顾名思义是一种总是选择当前最优的，以期望达到整体最优的方法贪心法一般用于求解最优化问题。采用贪心法求最优化问题的算法，一般都包含一系列步骤，每一步都有一组选择，每次都选择当前最优的选择，希望通过局部最优的选择达到全局最优的选择。贪心法不一定总能产生最优解，可能产生近似解甚至完全不正确的答案，故想使用贪心法，最好是能够能够符合贪心法产生优化解的条件。它的做法大致可以分为以下三步：
a、确定贪心策略
b、根据贪心策略，一步一步得到局部最优解
c、将局部最优解合并起来就得到全局最优解
贪心算法有几种典型的例子
一、活动安排问题
这类问题的贪心策略是使剩余时间最大化，要优先安排先结束的活动。具体做法是：每个活动是一个结构体：包含开始时间，结束时间，是否被安排过三个属性，按照结束时间升序排序，每次都选择可以相容的，结束时间最早的活动每次选取一个活动要考虑两个问题：结束时间是目前没有安排的活动中最早的，相容性，相容性是指在安排了上一个活动的基础上，这个活动还能安排得进去，这个活动的开始时间大于或者等于上一个已经安排好的活动的结束时间`

#include<bits/stdc++.h> using namespace std;
#define max_v 100 struct node
{
    int i;
    int end_time;
    int start_time;
    int flag;
};
bool cmp(node a,node b)
{
    return a.end_time<b.end_time;
}
int main()
{
    struct node p[max_v];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d %d",&p[i].i,&p[i].start_time,&p[i].end_time);
        p[i].i=i+1;
        p[i].flag=0;
    }
    sort(p,p+n,cmp);
    int sum=1;
    int end_time;
    end_time=p[0].end_time;
    p[0].flag=1;
    for(int i=1;i<n;i++)
    {
        if(p[i].start_time>=end_time)
        {
            sum++;
            p[i].flag=1;
            end_time=p[i].end_time;
        }
    }
    printf("sum=%d\n",sum);
    printf("活动编号：\n");
    for(int i=0;i<n;i++)
    {
        printf("%d ",p[i].i);
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

二 区间覆盖问题
6.区间覆盖问题
POJ1328是一道经典的贪心算法例题。题目大意是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。对于每个小岛，我们可以计算出一个雷达所在位置的区间。问题可以转化为如何用尽可能少的点覆盖这些区间。先将所有区间按照左端点大小排序，初始时需要一个点。如果两个区间相交而不重合，我们什么都不需要做；如果一个区间完全包含于另外一个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。

#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct Point
{
	double x;
	double y;
}point[1000];
 
int cmp(const void *a, const void *b)
{
    return (*(Point *)a).x>(*(Point *)b).x?1:-1;
}
 
int main()
{
	int n,d;
	int num=1;
	while(cin>>n>>d)
	{
		int counting=1;
		if(n==0&&d==0) break;
		for(int i=0;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			if(y>d)
			{
				counting=-1;
			}
			double t=sqrt(d*d-y*y);
			//转化为最少区间的问题 
			point[i].x=x-t;
			//区间左端点 
			point[i].y=x+t;
			//区间右端点 
		}
		if(counting!=-1)
		{
			qsort(point,n,sizeof(point[0]),cmp);
			//按区间左端点排序 
			double s=point[0].y;
			//区间右端点 
			for(int i=1;i<n;i++)
			{
				if(point[i].x>s)
				//如果两个区间没有重合,增加雷达数目并更新右端点 
				{
					counting++;
					s=point[i].y; 
				}
				else if(point[i].y<s)
				//如果第二个区间被完全包含于第一个区间,更新右端点 
				{
					s=point[i].y;
				}
			}
		}
		cout<<"Case "<<num<<':'<<' '<<counting<<endl;
		num++; 
	}
}	

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

三 小船过河问题
题目大意是只有一艘船，能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，问把n个人运到对岸，最少需要多久。先将所有人过河所需的时间按照升序排序，我们考虑把单独过河所需要时间最多的两个旅行者送到对岸去，有两种方式：
1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，所需时间为：t[0]+2t[1]+t[n-1]；
2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来，所需时间为：2t[0]+t[n-2]+t[n-1]。
算一下就知道，除此之外的其它情况用的时间一定更多。每次都运送耗时最长的两人而不影响其它人，问题具有贪心子结构的性质。

#include
#include
using namespace std;

int main()
{
int a[1000],t,n,sum;
scanf("%d",&t);
while(t–)
{
scanf("%d",&n);
sum=0;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
while(n>3)
{
sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);
n-=2;
}
if(n3) sum+=a[0]+a[1]+a[2];
else if(n2) sum+=a[1];
else sum+=a[0];
printf("%d\n",sum);
}

四、找零钱问题
小智去超市买东西，买了不超过一百块的东西。收银员想尽量用少的纸币来找钱。
纸币面额分为50 20 10 5 1 五种。请在知道要找多少钱n给小明的情况下，输出纸币数量最少的方案。 1<=n<=99

include<stdio.h>
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int a1, b, c, d, e;
		a1 = n / 50;
		b = (n-50*a1)/20;
		c = (n-50*a1-20*b)/10;
		d = (n-50*a1-20*b-10*c)/5;
		e = n-50*a1-20*b-10*c-5*d;
		int a[60] = {0};
		//printf("%d %d %d %d %d\n",a1,b,c,d,e); 
		a[50] = a1;a[20] = b;a[10] = c; a[5] = d; a[1] = e;
		int mark = 0;
		for(int i = 50; i > 0; i--)
		{
			if(a[i]!=0)
			{
				printf("%d*%d",i,a[i]);
				a[i] = 0;
				break;
			}
		 } 
		for(int i = 50; i > 0; i--)
	{
			if(a[i]!=0)
			{
				printf("+%d*%d",i,a[i]);			
			}
		} 
		printf("\n");	
	} 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

需要指出的是贪心在很多复杂题目中可能无法得到最优解，或者只是解题过程中很小的一步，需要具体题目具体分析