算法竞赛-- 贪心

发表于 更新于 分类于 阅读次数：
本文字数： 3.9k 阅读时长 ≈ 4 分钟

贪心:贪心法是求解一类最优化问题的方法,它总是考虑在当前状态下局部最优(或较优)的策略，来使全局的结果达到最优(或较优)。

贪心算法适用的问题一定满足最优子结构性质,即一个问题的最优解可以由它的子问题的最优解有效的构造出来.

1.区间不相交问题

给出N个开区间(x,y),从中选择尽可能多的开区间，使得这些开区间两两没有交集,

样例输入:

1
2
3
4
5
4
1 3
2 4
3 5
6 7

样例输出:

1
3

思路:总是选择左端点的最大区间.

代码如下:

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
#include <stdio.h>
#include <algorithm>
struct Interval
{
	int x1,x2;
}I[105];
using namespace std;
bool cmp(Interval a,Interval b)//排序规则,对左端点进行从大到小排序,左端点相同右端点从小到大排序.
{
	if(a.x1!=b.x1)
		return a.x1>b.x1;
	else
		return a.x2<b.x2;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d %d",&I[i].x1,&I[i].x2);
	sort(I,I+n,cmp);
	int count=1,last=I[0].x1;		//count记录不相交区间的个数,last记录上一个被选中区间的左端点.
	for(int i=1;i<n;i++)
	{
		if(I[i].x2<=last)	//如果该区间的右端点小于等于上一被选中区间的左端点。last更新一次，个数更新一次.
		{
			last=I[i].x1;
			count++;
		}
	}
	printf("%d\n",count);
	return 0;
}

与该题相似的为 区间选点问题。

给出N个闭区间[x,y],求最少需要确定多少个点,才能使每个闭区间中至少存在一个点。

只需将 I[i].x2<=last 改为I[i].x2<last即可.

2.看电视

暑假到了，小明终于可以开心的看电视了。但是小明喜欢的节目太多了，他希望尽量多的看到完整的节目。

现在他把他喜欢的电视节目的转播时间表给你，你能帮他合理安排吗？

输入信息:

输入包含多组测试数据。每组输入的第一行是一个整数n（n<=100），表示小明喜欢的节目的总数。

接下来n行，每行输入两个整数si和ei（1<=i<=n），表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。

当n=0时，输入结束。

输出信息:

对于每组输入，输出能完整看到的电视节目的个数。

样例输入:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

样例输出:

1
5

思路:该题即为区间不想交问题.

代码如下:

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
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Interval
{
	int x1,x2;
}I[105];
bool cmp(Interval a,Interval b)
{
	if(a.x1!=b.x1)
		return a.x1>b.x1;
	else
		return a.x2<b.x2;
}
int main()
{
	int n;
	while(scanf("%d",&n)==1 && n)
	{
		for(int i=0;i<n;i++)
			scanf("%d %d",&I[i].x1,&I[i].x2);
		sort(I,I+n,cmp);
		int count=1,last=I[0].x1;
		for(int i=1;i<n;i++)
		{
			if(I[i].x2<=last)
			{
				count++;
				last=I[i].x1;
			}
		}
		printf("%d\n",count);
	}
	return 0;
}

5.数列

编写一个求斐波那契数列的递归函数，输入n 值，使用该递归函数，输出如下图形（参见样例）。

输入信息:

输入第一行为样例数m，接下来有m行每行一个整数n，n不超过10。

输出信息:

对应每个样例输出要求的图形(参见样例格式)。
输出只有1行，即名名吃巧克力的方案数。

样例输入:

1
2
1
6

样例输出:

1
2
3
4
5
6
          0
        0 1 1
      0 1 1 2 3
    0 1 1 2 3 5 8
  0 1 1 2 3 5 8 13 21
0 1 1 2 3 5 8 13 21 34 55

思路:该题利用斐波那切数列解题，输出m行数，每行从第0项开始，总共2m-1个数。

代码如下:

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
#include <stdio.h>
int ff(int n)
{
	if(n==0)
		return 0;
	else if(n==1)
		return 1;
	else
		return ff(n-1)+ff(n-2);
}
int main()
{
	int n,m;
	while(scanf("%d",&n)==1)		//测试样例数
	{
		for(int k=0;k<n;k++)
		{
			scanf("%d",&m);		//输入m
			for(int i=1;i<=m;i++) 	//输出m行
			{
				for(int j=0;j<2*(m-i);j++)//输出空格
					printf(" ");
				for(int j=0;j<2*i-1;j++)	//输出数字
				{
					printf("%d",ff(j));
					if(j<2*(i-1))
						printf(" ");	
				}
				printf("\n");
			}
		}	
	}
	return 0;
}

6.神奇的口袋

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

输入信息:

输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。

输出信息:

输出不同的选择物品的方式的数目。

样例输入:

1
2
3
4
5
6
7
2
12
28
3
21
10
5

样例输出:

1
2
1
0

思路:从0开始,思路是用40减去good[0]，然后用余数继续与后面数组中的元素相减，看结果是否为0，若为0，表示这样排列满足条件，count++。若不为0，则继续往下走，直到余数小于0或者数组中的数已经全部读完，这样一次查找就完成了，接着需要回退到上一步去继续寻找下一个包含good[0]的可能组合。就比如进行到40-good[0]-good[1]时发现余数为0满足条件，count+1，然后回退到40-good[0]，跳过good[1]，去检查40-good[0]-good[2]是否满足条件，如此往复，直到检查到40-good[0]-good[n-1]为止

代码如下:

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
#include <stdio.h>
int good[25];
int count,r=40,n;
void g(int index)
{
	if(r<0)
		return;
	else if(r==0)
	{
		count++;
		return;
	}
	if(index==n)
		return;
	for(int x=index;x<n;x++)
	{
		r=r-good[x];
		g(x+1);
		r=r+good[x];
	}	
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		count=0;
		for(int i=0;i<n;i++)
			scanf("%d",&good[i]);	//输入物体的体积
		g(0);						//递归开始
		printf("%d\n",count);
	}
	return 0;
}
小礼物走一个哟
0%