Heim > Backend-Entwicklung > C++ > C-Programm für Aktivitätsauswahlproblem

C-Programm für Aktivitätsauswahlproblem

王林
Freigeben: 2023-09-11 22:13:02
nach vorne
566 Leute haben es durchsucht

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
Nach dem Login kopieren

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]
Nach dem Login kopieren

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;
}
Nach dem Login kopieren

Ausgabe

Following activities are selected 0 2
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage