アクティビティ選択問題、アクティビティ選択
問題の説明:
n 個のアクティビティ E={1,2,…,n} のセットがあり、それぞれが講義会場などの同じリソースの使用を必要とし、このリソースを使用できるアクティビティは 1 つだけであるとします。同じ時間です。各アクティビティ i には、リソースの使用を必要とする開始時刻 si と終了時刻 fi があり、si
。
この図から、S には 11 個のアクティビティがあることがわかります。相互に互換性のあるアクティビティの最大のサブセットは、{a1 、a4 、a8 、a11,}、および {a2 です。 、a4 、a9 、a11 }。
2. 動的プログラミングのソリューションプロセス
(1) アクティビティ選択問題の最適部分構造
部分問題解空間 Sij を S の部分集合として定義し、それぞれが互いに互換性を持つようにします。つまり、各アクティビティは ai が終了した後に開始され、aj が開始する前に終了します。
議論とその後の計算を容易にするために、2 つの架空のアクティビティ a0 と an+1 を追加します。 ここで f0 =0 と sn+1 =∞。
結論: i≥j の場合、Sij は空集合です。
アクティビティが終了時間順に単調増加でソートされている場合、サブ問題空間を使用して、Sij からアクティビティの互換性のある最大のサブセットを選択します。ここで、0≤i＜j≤n+1であるため、他のSij は空集合です。
最適な部分構造は次のとおりです: Sij の最適解Aij にアクティビティak が含まれていると仮定すると、Sik の解Aik とSkjの解A kj 最高でなければなりません。
問題はアクティビティ ak を通じて 2 つの部分問題に分割され、次の式で Sij の解 Aij を計算できます。
(2) 再帰的な解決策
Sij の最大の互換性のあるサブセット内のアクティビティの数を c[i][j] とします。Sij が空集合のとき、c[i][j]=0 になります。は空ではありません。 ak がSij の互換性のある最大サブセットで使用されている場合、問題Sik とSkj の互換性のある最大サブセットも使用されるため、c[iを取得できます][j ] = c[i][k]+c[k][j]+1。
i≥j の場合、S
ij は空集合でなければなりません。それ以外の場合、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 使用 名前空間 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 温度;
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]=温度;
25 ret[i][j]=k;
26 }
27 }
28 }
29 }
30 }
31
32 int main()
33 {
34 int n;
35 printf(" 输入活动个数 n: " );
36 ながら (~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(" 最大子コレクションの数=%dn " ,c[1 ][n]+2 );
48 戻る 0 ;
49 }
コードを表示
次は贪心法の代コード：
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 名前空間 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 ながら (~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 }
コードを表示
http://www.bkjia.com/PHPjc/1069127.html www.bkjia.com 本当 http://www.bkjia.com/PHPjc/1069127.html 技術記事 アクティビティ選択問題、アクティビティ選択問題の説明: n 個のアクティビティ E={1,2,,n} の集合があり、それぞれは講義会場などの同じリソースの使用を必要とします。同時にあるのは... .
