活動選擇問題，活動選擇
問題描述：
設有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 }
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("\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 }
View Code
