贪心算法——C语言

习该博主「houjingyi233」的贪心算法而感：
原文链接：https://blog.csdn.net/qq_32400847/article/details/51336300

贪心/贪婪算法的主要思想就是局部最优——>全局最优，这并不是一个比较难理解的概念，然后我经过相关的题目案例发现难点在于求得每一个局部最优解的算法。

心算法的定义：
1.活动选择问题：
有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。

每个活动ai都有一个开始时间si和结束时间fi 。

一旦被选择后，活动ai就占据半开时间区间[si,fi)。

如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。

该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。

#include
#include

struct  Act{
	int start;
	int end;

}act[1000];

/*活动选择问题*/ 

void sort(Act act[],int n);
int explore(Act act[],int n);


int main()
{
	 int n;
	 scanf("%d",&n);
	 for(int i=0;i<n;i++)
	 {
	 	scanf("%d%d",&act[i].start,&act[i].end);
	 }
	 //将每个活动根据其结束时间进行从小到大的排序 
	sort(act,n);
	//根据贪心算法求出选择每个活动的最优时间
	int num=explore(act,n); 
	printf("一天中选择可进行活动最大的数量为：%d",num);
	return 0;
}

void sort(Act act[],int n)
{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n-i-1;j++)
			{	
				if(act[j].end>act[j+1].end)
				{
					Act temp=act[j];
					act[j]=act[j+1];
					act[j+1]=temp;
				}
			}
		}
 } 
int explore(Act act[],int n)
{
	int result=1;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(act[i].end<act[j].start)  //所有活动都已根据结束时间从小到大排序，所以现在只需要根据前一个活动的结束时间 ， 
			{                            //所以现在只需要根据前一个活动的结束时间大于后一个活动的开始时间即可安排进行。

 
				result++;
				i=j;
			}
		}
	}
	return result;
}

2.钱币找零问题
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。

现在要用这些钱来支付K元，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。

#include
#include

int main() {
	int m[7]= {1,2,5,10,20,50,100}; //先有纸币的数额
	int k;
	//所找的金额
	int num;          //所需纸币的张数
	while((	scanf("%d",&k))!=EOF) {
		while(k>0) {
			if(k>=100) {
				k-=100;
			} else if(k>=50&&k<100) {
				k-=50;
			} else if(k>=20&&k<50) {
				k-=20;
			} else if(k>=5&&k<20) {
				k-=5;
			} else if(k>=2&&k<5) {
				k-=2;
			} else if(k>=1&&k<2) {
				k-=1;
			}
			num++;
		}
		printf("所需的张数为：%d\n",num);
	}
}

3.再论背包问题
4.多机调度问题
5.小船过河问题
6.区间覆盖问题
给定一个长度为m的区间，再给出n条线段的起点和终点（注意这里是闭区间），求最少使用多少条线段可以将整个区间完全覆盖
注：该代码只能通过部分案例，问题我来日再来解决！！！

#include
#include
//测试数据：8 7   1 6 3 4 3 6 3 7 6 8 2 4 3 5

struct Line {  //表示每条线段的左右区间的值
	int x;
	int y;

};

void sort(Line l[],int n);       //将每一个区间按照左端点递增的顺序排序
int  search(Line l[],int n,int m) ;
int main() {
	//m为区间长度，n为线段条数
	int m,n;
	scanf("%d%d",&m,&n);
	Line l[n];
	for(int i=0; i<n; i++) {
		scanf("%d%d",&l[i].x,&l[i].y);
	}
	sort(l,n);
	int num;
	num=search(l,n,m);
	printf("%d",num);
	return 0;
}

void sort(Line l[],int n) {
	for(int i=0; i<n; i++) {
		for(int j=0; j<n-i-1; j++) {
			if(l[j].x>l[j+1].x) {
				Line temp=l[j];
				l[j]=l[j+1];
				l[j+1]=temp;
			}
		}
	}
}
int  search(Line l[],int n,int m) {
	int i=0;
	int ans=0,max=0,r=l[0].x;
	for(i=0; i<n; i++) {
		if(l[i].x<=r) {
			for(int j=i; j<m; j++) {
				if(l[j].x<=r&&l[j].y>r&&l[j].x>max) {
					max=l[j].y;
					i=j;
				}
			}
			r=max;
			max=0;
			ans++;
		}
		if(r>=m) {
			break;
		}
	}
	if(r<m) {
		return 0;
	} else {
		return ans;
	}

}