Der gierige Algorithmus ist ein Algorithmus, der in jedem Schritt die beste (als Teil des aktuellen Schritts) Option bei der Berechnung wählt, dass die endgültige Entscheidung global optimal sein wird.
Ein kleines Beispiel:
Lassen Sie uns eine unbegrenzte Anzahl von Münzen verschiedener Nominierten haben, und wir müssen S erhöhen. Wir werden zwei konkrete Fälle untersuchen, von denen jeder versuchen wird, den Gieralgorithmus zu lösen.
Lassen Sie uns damit fortfahren: Wir nehmen die Münze, die größte nominale (optimale Option innerhalb des Schrittes) bei jedem Schritt, die den Restbetrag nicht überschreitet.
a) Mögen die Nominierten 1, 5 und 10 und S = 27.
(1) Nehmen Sie 10, S: 27 - Zustand 17
(2) Nehmen Sie 10, S: 17 - Zustand 7
(3) Wir nehmen 5, S: 7 - Zustand 2
(4) Nehmen Sie 1, S: 2 - Zustand 1
(5) Nehmen Sie 1, S: 1 - Zustand 0
Sie haben schließlich fünf Münzen. Sie können sicherstellen, dass allein (z.B. Schott) vier Münzen oder weniger 27 nicht funktionieren.
b) Mögen die Nonnen 1, 5 und 7 und S = 24.
(1) Nehmen 7, S: 24 - Zustand 17
(2) Nehmen Sie 7, S: 17 - Zustand 10
(3) Nehmen Sie 7, S: 10 - Zustand 3
(4) Nehmen Sie 1, S: 3 - Zustand 2
(5) Nehmen Sie 1, S: 2 - Zustand 1
(6) Wir nehmen eins, S: 1 - Zustand 0.
Sie hatten sechs Münzen, aber sie hätten S vier Münzen wählen können - zwei Nominierten 7 und zwei Nominierten 5.
Der gierige Algorithmus ist nicht immer der Fall, wie aus dem Beispiel ersichtlich ist. Aber wenn es im Allgemeinen zu einer optimalen Reaktion führt, wäre es in der Regel einfacher als mit der dynamischen Programmierung oder anderen Methoden.