活动选择问题 (动态规划、贪心算法)

问题描述：

设有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个活动，最大的相互兼容的活动子集为:{a₁，a₄，a₈，a11，}和{a₂，a₄，a₉，a₁₁}。

2、动态规划解决过程

（1）活动选择问题的最优子结构

定义子问题解空间S_ij是S的子集，其中的每个获得都是互相兼容的。即每个活动都是在a_i结束之后开始，且在a_j开始之前结束。

为了方便讨论和后面的计算，添加两个虚构活动a₀和a_n+1，其中f₀=0，s_n+1=∞。

结论：当i≥j时，S_ij为空集。

如果活动按照结束时间单调递增排序，子问题空间被用来从S_ij中选择最大兼容活动子集，其中0≤i＜j≤n+1，所以其他的S_ij都是空集。

最优子结构为：假设S_ij的最优解A_ij包含活动a_k，则对S_ik的解A_ik和S_kj的解A_kj必定是最优的。

通过一个活动a_k将问题分成两个子问题，下面的公式可以计算出S_ij的解A_ij。

（2）一个递归解

　　设c[i][j]为S_ij中最大兼容子集中的活动数目，当S_ij为空集时，c[i][j]=0；当S_ij非空时，若a_k在S_ij的最大兼容子集中被使用，则则问题S_ik和S_kj的最大兼容子集也被使用，故可得到c[i][j] = c[i][k]+c[k][j]+1。

当i≥j时，S_ij必定为空集，否则S_ij则需要根据上面提供的公式进行计算，如果找到一个a_k，则S_ij非空（此时满足f_i≤s_k且f_k≤s_j），找不到这样的a_k，则S_ij为空集。

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("
输入活动开始以及结束时间
");
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
",c[1][n]+2);
48     return 0;
49 }

View Code

下面是贪心法的代码：

 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("
输入活动开始以及结束时间
");
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("
");
44     }
45 }

View Code