アクティビティ選択問題用の C プログラム

#アクティビティ選択問題は、一連のアクティビティとその開始時刻と終了時刻が与えられた場合に発生する問題です。人が 1 つのアクティビティを同時に実行できるすべてのアクティビティを見つける必要があります。

この問題では、次に実行するアクティビティを選択する貪欲なアルゴリズムを指定します。まずは 貪欲なアルゴリズム を理解しましょう。

貪欲アルゴリズムは、段階的に解決策を見つけることで問題の解決策を見つけようとするアルゴリズムです。次のステップを選択するために、アルゴリズムは最も有望と思われるステップ、つまり、残りのステップと比較してすぐに最適化されたソリューションにつながるステップも選択します。貪欲アルゴリズムは、次の中間ステップの最適な解決策を見つけようとするため、最適化問題を解決するために使用され、問題全体の最適な解決策につながります。

貪欲アルゴリズムは優れたソリューションですが、適用を妨げる問題がいくつかあります。たとえば、0-1 のナップザックは、貪欲なアルゴリズムを使用して解決することはできません。

アルゴリズム

標準的な貪欲アルゴリズムには、-

1) Dijkstrata’s Shortest Path
2) Minimum Spanning Tree (MST) {prim’s and kruskal’s}
3) Huffman coding

非アクティブ選択問題があり、開始時間と終了時間に関する n 個の問題が与えられます。人が一度に 1 つのアクティビティしか実行できないと仮定して、人が実行できるアクティビティの最大数を選択する必要があります。

アクティビティは終了時間順に 3 つあります。

Start = [1 , 5 , 12 ]
End = [10, 13, 23]

ここでは、最大 2 つのアクティビティを実行できます。実行できるアクティビティは [0, 2] です。

例

デモンストレーション

#include<stdio.h>
int main(){
   int start[] = {1 , 5 , 12};
   int finish[] = {10, 13, 23};
   int activities = sizeof(start)/sizeof(start[0]);
   int i, j;
   printf ("Following activities are selected \t");
   i = 0;
   printf("%d\t", i);
   for (j = 1; j < activities; j++){
      if (start[j] >= finish[i]){
         printf ("%d ", j);
         i = j;
      }
   }
   return 0;
}

出力

Following activities are selected 0 2

以上がアクティビティ選択問題用の C プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。