活动选择问题，活动选择
问题描述：
设有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
Stellungnahme： Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
