活动选择问题，活动选择
问题描述：
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si
。
从图中可以看出S中共有11个活动，最大的相互兼容的活动子集为:{a1 ，a4 ，a8 ，a11，}和{a2 ，a4 ，a9 ，a11 }。
2、动态规划解决过程
（1）活动选择问题的最优子结构
定义子问题解空间Sij 是S的子集，其中的每个获得都是互相兼容的。即每个活动都是在ai 结束之后开始，且在aj 开始之前结束。
为了方便讨论和后面的计算，添加两个虚构活动a0 和an+1， 其中f0 =0，sn+1 =∞。
结论：当i≥j时，Sij 为空集。
如果活动按照结束时间单调递增排序，子问题空间被用来从Sij 中选择最大兼容活动子集，其中0≤i＜j≤n+1，所以其他的Sij 都是空集。
最优子结构为：假设Sij 的最优解Aij 包含活动ak ，则对Sik 的解Aik 和Skj 的解Akj 必定是最优的。
通过一个活动ak 将问题分成两个子问题，下面的公式可以计算出Sij 的解Aij 。
（2）一个递归解
设c[i][j]为Sij 中最大兼容子集中的活动数目，当Sij 为空集时，c[i][j]=0；当Sij 非空时，若ak 在Sij 的最大兼容子集中被使用，则则问题Sik 和Skj 的最大兼容子集也被使用，故可得到c[i][j] = c[i][k]+c[k][j]+1。
当i≥j时，Sij 必定为空集，否则Sij 则需要根据上面提供的公式进行计算，如果找到一个ak ，则Sij 非空（此时满足fi ≤sk 且fk ≤sj ），找不到这样的ak ，则Sij 为空集。
c[i][j]的完整计算公式如下所示：
亲测代码:
1 #include
2 #define max_size 10010
3 int s[max_size];
4 int f[max_size];
5 int c[max_size][max_size];
6 int ret[max_size][max_size];
7
8 using namespace std;
9
10 void DP_SELECTOF(int *s,int *f,int n,int c[][max_size],int ret[][max_size])
11 {
12 int i,j,k;
13 int temp;
14 for (j=2 ;j)
15 for (i=1 ;i)
16 {
17 for (k=i+1 ;k)
18 {
19 if (s[k]>=f[i]&&f[k]s[j])
20 {
21 temp=c[i][k]+c[k][j]+1 ;
22 if (c[i][j]temp)
23 {
24 c[i][j]=temp;
25 ret[i][j]=k;
26 }
27 }
28 }
29 }
30 }
31
32 int main()
33 {
34 int n;
35 printf(" 输入活动个数 n: " );
36 while (~scanf(" %d " ,&n))
37 {
38 memset(c,0 ,sizeof (0 ));
39 memset(ret,0 ,sizeof (ret));
40 printf(" \n输入活动开始以及结束时间\n " );
41 int i,j;
42 for (i=1 ;i)
43 {
44 scanf(" %d%d " ,&s[i],&f[i]);
45 }
46 DP_SELECTOF(s,f,n,c,ret);
47 printf(" 最大子集的个数=%d\n " ,c[1 ][n]+2 );
48 return 0 ;
49 }
View Code
下面是贪心法的代码：
1 #include
2 #define max_size 10010
3 int s[max_size];
4 int f[max_size];
5 int ret[max_size];
6 int c[max_size][max_size];
7 using namespace std;
8
9 void GREEDY_ACTIVITY_SELECTOR(int *s,int *f,int n,int *ret)
10 {
11 int k,m;
12 *ret++=1 ;
13 k=1 ;
14 for (m=2 ;m)
15 if (s[m]>=f[k])
16 {
17 *ret++=m;
18 k=m;
19 }
20 }
21 int main()
22 {
23 int n;
24 printf(" 输入活动个数 n: " );
25 while (~scanf(" %d " ,&n))
26 {
27 memset(s,0 ,sizeof (s));
28 memset(f,0 ,sizeof (f));
29 memset(c,0 ,sizeof (0 ));
30 memset(ret,0 ,sizeof (ret));
31 printf(" \n输入活动开始以及结束时间\n " );
32 int i,j;
33 for (i=1 ;i)
34 {
35 scanf(" %d%d " ,&s[i],&f[i]);
36 }
37 GREEDY_ACTIVITY_SELECTOR(s,f,n,ret);
38 for (i=0 ;i)
39 {
40 if (ret[i]!=0 )
41 printf(" a%d " ,ret[i]);
42 }
43 printf(" \n " );
44 }
45 }
View Code
