回溯法之活动安排问题

回溯法之活动安排问题

1.问题：假设有一个需要使用某一资源的n个活动所组成的集合S，S={1，…，n}。该资源任何时刻只能被一个活动所占用，活动i有一个开始时间bi和结束时间ei（bi<ei），其执行时间为ei-bi，假设最早活动执行时间为0。一旦某个活动开始执行，中间不能被打断，直到其执行完毕。若活动i和活动j有bi≥ej或bj≥ei，则称这两个活动兼容。设计算法求一种最优活动安排方案，使得所有安排的活动个数最多。

2.设计思路：采用回溯法求解，相当于找到S={1，…，n}的某个排列即调度方案，使得其中所有兼容活动个数最多，对应的解空间是一个是排列树。直接采用排列树递归框架实现，对于每一种调度方案求出所有兼容活动个数，通过比较求出最多活动个数maxsum，对应的调度方案就是最优调度方案bestx，即为本问题的解。

3.代码：

/*回溯法之活动安排问题*/
#include <stdio.h>
#define MAXN 51
struct Action
{int b;								//开始时间int e;								//结束时间
};
int n = 4;
Action A[] = { {0,0},{1,3},{2,5},{4,8},{6,10} };			//数组下标0不用 
int x[MAXN];							//临时解向量
int bestx[MAXN];						//最优解向量
int laste = 0;							//结束时间
int sum = 0;							//一个方案中最多兼容的活动个数 
int maxsum = 0;							//最终方案中最多兼容的活动个数 void swap(int &x,int &y)				//交换x,y
{int temp=x;x=y;y=temp;}void dispasolution()					//输出最优解 
{int laste = 0;for (int j = 1; j <= n; j++){if (A[bestx[j]].b >= laste){printf("选取活动%d[%d,%d]\n",bestx[j],A[bestx[j]].b,A[bestx[j]].e);laste = A[bestx[j]].e;						//更改为当前活动的结束时间}}printf("活动安排的个数=%d\n",maxsum);
}void dfs(int i)										//搜索问题的最优解 
{if (i > n)										//达到叶子节点产生一种方案 {if (sum > maxsum){maxsum = sum;for (int j = 1; j <= n; j++)bestx[j] = x[j];}}else											 {for (int j = i; j <= n; j++)				//没有到叶子节点，考虑i到n的活动{swap(x[i], x[j]);						//交换x[i],x[j] int sum1 = sum;							//保存sum、laste以便回溯 int laste1 = laste;if (A[x[j]].b >= laste)					//开始时间大于当前结束时间{sum++;								//兼容活动的个数加1	laste = A[x[j]].e;					//修改本方案的最后结束时间 }dfs(i + 1);								//回溯swap(x[i], x[j]);sum = sum1;						//撤销第i层对活动x[j]的选择，以便选择全球通活动 laste = laste1;}}
}int main()
{for(int i=1;i<=n;i++){x[i]=i;} dfs(1);								//从i=1开始搜索 dispasolution();					//输出结果return 0; } 

4.运行结果：