C-Programm für Aktivitätsauswahlproblem

Das Problem der Aktivitätsauswahl ist ein Problem, bei dem eine Reihe von Aktivitäten und deren Start- und Endzeiten gegeben sind. Wir müssen alle Aktivitäten finden, die eine Person ausführen kann, indem sie eine einzelne Aktivität gleichzeitig ausführt.

Dieses Problem gibt einen gierigen Algorithmus an, um die nächste auszuführende Aktivität auszuwählen. Lassen Sie uns zunächst den „Greedy-Algorithmus“ verstehen.

Der Greedy-Algorithmus

ist ein Algorithmus, der versucht, eine Lösung für ein Problem zu finden, indem er Schritt für Schritt eine Lösung findet. Um den nächsten Schritt auszuwählen, wählt der Algorithmus auch den Schritt aus, der am erfolgversprechendsten erscheint, also im Vergleich zu den anderen sofort zu einer optimierten Lösung führt. Der Greedy-Algorithmus wird zur Lösung von Optimierungsproblemen verwendet, da er versucht, die optimalste Lösung für den nächsten Zwischenschritt zu finden, was zur optimalen Lösung des gesamten Problems führt. Obwohl der Greedy-Algorithmus eine gute Lösung ist, gibt es einige Probleme, die seine Anwendung verhindern. Beispielsweise kann der 0-1-Rucksack nicht mit einem Greedy-Algorithmus gelöst werden.

Algorithmus

Einige Standard-Greedy-Algorithmen sind -

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

Inaktives Auswahlproblem, wir haben n Probleme mit der Start- und Endzeit. Wir müssen die maximale Anzahl von Aktivitäten auswählen, die eine Person ausführen kann, unter der Annahme, dass sie jeweils nur eine Aktivität ausführen kann.

Es gibt 3 Aktivitäten, sortiert nach ihrer Endzeit,

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

Hier kann man bis zu zwei Aktivitäten durchführen. Die ausführbaren Aktivitäten sind [0, 2].

Beispiel

Demonstration

#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;
}

Ausgabe

Following activities are selected 0 2

Das obige ist der detaillierte Inhalt vonC-Programm für Aktivitätsauswahlproblem. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!