活動選択問題のための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