会议安排（贪心算法和动态规划）_会议安排 动态规划

1.问题：假设要在一个教室里安排一批活动，并希望使用尽可能多的安排活动。设计一个有效的算法进行安排。

2.1.贪心算法：一开始选择活动1，然后把剩下的活动按结束时间递增进行排序，以后的活动与s[i]进行比较，如果可以安排就安排此活动，因为活动已经按结束时间递增进行了排序，所以被选择的活动是可以选择活动中结束时间最早的。此处的贪心策略是每一次都选择可以上和上一个活动相容，而且结束时间最早的活动进行安排。

2.2动态规划：设计思路:首先把活动按结束时间最早进行递增排序；dp[i]记录活动以活动i为结尾的最大活动安排数,如果event[i].begin>=event[i-1].end,那么活动i可以被安排上，dp[i]=dp[i-1]+1；如果event[i].begin<event[i-1].end,那么活动i无法被安排，dp[i]=dp[i-1]；另外用一个数组path[j]去记录最优解的路径，自底向上if(dp[i]>dp[i-1]),说明活动event[i].number被选了，path[j]=event[i].number;

3.1.贪心算法代码：

/*贪心算法之活动安排问题*/
#include <stdio.h>
typedef struct{			//活动具有的属性 
	int begin;
	int end;
	int number;			//记录是第几个活动 
}activity;
 
#define	N 11 
int start[N]={1,3,0,5,3,5,6,8,8,2,12};			//活动开始的时间 
int end[N]={4,5,6,7,8,9,10,11,12,13,14};			//活动结束的时间 
activity event[100];
 
void Sort(activity *array)			//除了第一个活动，将剩下的活动按结束时间最早进行排序 
{
	activity temp;
	for(int i=1;i<N;i++)		//简单的冒泡排序 
	{
		for(int j=i+1;j<N;j++)
		{
			if(event[i].end>event[j].end)
			{
				temp=event[i];
				event[i]=event[j];
				event[j]=temp;
			}
		}
	}
}
 
void Greedy(activity *array)						//贪婪策略 
{
	int count=1;
	printf("可以安排的最大活动如下：\n");
	printf("活动1  ");
	for(int i=0;i<N;i++)		 
	{
		for(int j=i+1;j<N;j++)
		{
			if(array[j].begin>=array[i].end)//下一个活动的开始时间大于当前活动的结束时间表示可以相容 
			{
				//printf("test1\n");
				printf("活动%d\t",array[j].number); 
				i=j;						//把当活动的位置移动到j,方便下一次的比较 
				count++;
				break;
			}
		}
	}
	printf("----->总共可以安排%d个会议\n",count);
 } 
 
int main()
{
	for(int i=0;i<N;i++)
	{
		event[i].begin=start[i];
		event[i].end=end[i];
		event[i].number=i+1;
	}
	Sort(event);
	for(int i=0;i<N;i++)
	{
		printf("%d\t",event[i].number);
	}
	printf("\n");
	for(int i=0;i<N;i++)
	{
		printf("%d\t",event[i].begin);
	}
	printf("\n");
	for(int i=0;i<N;i++)
	{
		printf("%d\t",event[i].end);
	}
	printf("\n");
	Greedy(event);
	return 0; 
 } 

3.2.动态规划代码：

/*动态规划之活动安排*/
#include <stdio.h>
typedef struct{			//活动具有的属性 
	int begin;
	int end;
	int number;			//记录是第几个活动 
}activity;
 
#define	N 12 
int start[N]={0,1,3,0,5,3,5,6,8,8,2,12};			//活动开始的时间 
int end[N]={0,4,5,6,7,8,9,10,11,12,13,14};			//活动结束的时间 
activity event[100];
int dp[N];										//记录以i为结尾的最大活动安排数 
int path[N];									//记录最优解的路径 
 
void Sort(activity *array)			//除了第一个活动，将剩下的活动按结束时间最早进行排序 
{
	activity temp;
	for(int i=1;i<N;i++)		//简单的冒泡排序 
	{
		for(int j=i+1;j<N;j++)
		{
			if(event[i].end>event[j].end)
			{
				temp=event[i];
				event[i]=event[j];
				event[j]=temp;
			}
		}
	}
}
 
void Dynamic(activity *array)		//动态规划算法 
{
	bool flag; 
	for(int i=2;i<N;i++)
	{
		flag=false;							//标志变量，判断是否找到相容的活动 
		for(int j=i-1;j>0;j--)
		{
			if(event[i].begin>=event[j].end)		//从前往后遍历，直到找到可以相容的活动 
			{
				dp[event[i].number]=dp[event[j].number]+1;//最优解为前一个最优解+1 
				flag=true;						//flag=true,说明活动j找到可以相容的活动 
				break;
			}
		}
		if(flag==false)	//如果flag=false，说明没有找到相容的活动，
		{				 //此活动为结尾的最优解，为以其前面一个活动为结尾的最优解 
			dp[event[i].number]=dp[event[i-1].number];
		 } 
	 } 
}
 
int main()
{
	dp[0]=0;
	dp[1]=1;
	int max=0;							//记录可以安排的最大活动数 
	for(int i=0;i<N;i++)
	{
		event[i].begin=start[i];
		event[i].end=end[i];
		event[i].number=i;
	}
	Sort(event);
	for(int i=0;i<N;i++)
	{
		printf("%d\t",event[i].number);
	}
	printf("\n");
	for(int i=0;i<N;i++)
	{
		printf("%d\t",event[i].begin);
	}
	printf("\n");
	for(int i=0;i<N;i++)
	{
		printf("%d\t",event[i].end);
	}
	printf("\n");
	Dynamic(event); 
	//Greedy(event);
	printf("dp[0]=%d\n",dp[0]);
	printf("dp[]数组如下：\n");
	for(int i=0;i<N;i++)
	{	printf("%d--",event[i].number);
		printf("%d\t",dp[event[i].number]);
		if(dp[event[i].number]>max)
		{
			max=dp[event[i].number];
		}
	 } 
	printf("\n可以安排的最大活动数为：%d\n",max);
	
	int amount=0;
	for(int i=N-1;i>=0;i--)
	{
		if(dp[event[i].number]>dp[event[i-1].number])
		{
			path[amount++]=event[i].number;
		}
	}
	printf("被选择的活动如下：\n");
	for(int i=amount-1;i>=0;i--)
	{
		printf("%d\t",path[i]);
	}
	return 0; 
 } 

4.1.贪心算法运行结果：

4.2动态规划运行结果：

 5.总结：

在会议安排上，贪心算法和动态规划的结果是一样的，而且贪心算法比较简单，所以一般面对会议安排问题时，使用贪心算法进行求解；动态规划的问题总结下来都是去求解：最优解和最优解的路径；动态规划的难题非常多，希望自己多通过练习可以学习更多的经验。0.0