アクティビティ選択の問題、アクティビティ選択_PHP チュートリアル

アクティビティ選択問題、アクティビティ選択

問題の説明:

n 個のアクティビティ E={1,2,…,n} のセットがあり、それぞれが講義会場などの同じリソースの使用を必要とし、このリソースを使用できるアクティビティは 1 つだけであるとします。同じ時間です。各アクティビティ i には、リソースの使用を必要とする開始時刻 si と終了時刻 fi があり、si

。

この図から、S には 11 個のアクティビティがあることがわかります。相互に互換性のあるアクティビティの最大のサブセットは、{a₁、a₄、a₈、a11,}、および {a₂ です。 、a₄、a₉、a₁₁}。

2. 動的プログラミングのソリューションプロセス

(1) アクティビティ選択問題の最適部分構造

部分問題解空間 S_ij を S の部分集合として定義し、それぞれが互いに互換性を持つようにします。つまり、各アクティビティは a_i が終了した後に開始され、a_j が開始する前に終了します。

議論とその後の計算を容易にするために、2 つの架空のアクティビティ 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の解Akj 最高でなければなりません。

問題はアクティビティ a_k を通じて 2 つの部分問題に分割され、次の式で S_ij の解 A_ij を計算できます。

(2) 再帰的な解決策

S_ij の最大の互換性のあるサブセット内のアクティビティの数を c[i][j] とします。S_ij が空集合のとき、c[i][j]=0 になります。は空ではありません。 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 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.htmlwww.bkjia.com本当http://www.bkjia.com/PHPjc/1069127.html技術記事アクティビティ選択問題、アクティビティ選択問題の説明: n 個のアクティビティ E={1,2,,n} の集合があり、それぞれは講義会場などの同じリソースの使用を必要とします。同時にあるのは... .