问题描述：
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
。
从图中可以看出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 <bits/stdc++.h> 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<=n;j++)15 for(i=1;i<j;i++)16 {17 for(k=i+1;k<j;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<=n;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 }
下面是贪心法的代码：
1 #include <bits/stdc++.h> 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<=n;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<=n;i++)34 {35 scanf("%d%d",&s[i],&f[i]);36 }37 GREEDY_ACTIVITY_SELECTOR(s,f,n,ret);38 for(i=0;i<=n;i++)39 {40 if(ret[i]!=0)41 printf("a%d ",ret[i]);42 }43 printf("\n");44 }45 }