Wann ein gieriger Algorithmus scheitert
Kurz gesagt: Ein gieriger Algorithmus scheitert, wenn die jetzt beste Wahl eine bessere Antwort später versperrt; ein Gegenbeispiel genügt, und die Korrektur ist oft dynamische Programmierung.
Problem
Ein Gutschein zu viel
Der Shop zahlt Treuepunkte als Gutscheine zu 4, 3 und 1 Punkt aus. Jeder Gutschein ist ein eigener Code, den der Kunde an der Kasse eintippt. Das Programm gibt also so wenige Gutscheine wie möglich aus: jedes Mal den größten, der passt, wie beim Wechselgeld in Euro-Münzen in der vorigen Lektion.
static List<Integer> greedy(int[] vouchers, int points) { List<Integer> used = new ArrayList<>(); for (int v : vouchers) { while (points >= v) { used.add(v); points -= v; } } return used;}int[] vouchers = {4, 3, 1};System.out.println("6 Punkte: " + greedy(vouchers, 6));6 Punkte: [4, 1, 1]Drei Codes für 6 Punkte. Dabei sind 3 + 3 zwei. Das Programm hat keinen Fehler im Code: Die Regel „der größte, der passt“ stimmt für diese Gutscheine einfach nicht. Bei Euro-Münzen stimmt sie, hier nicht.
Die Idee
Gierig geht nicht zurück
Ein gieriger Algorithmus trifft bei jedem Schritt die Wahl, die jetzt am besten aussieht, und überdenkt sie nie. Hat er einmal 4 genommen, bleiben für die restlichen 2 Punkte nur Gutscheine zu 1 Punkt. Dass 3 + 3 besser ist, sieht gierig nicht: Es probiert nichts anderes.
Eine gierige Idee wird also nur mit einem Beweis angenommen, dass die lokale Wahl nie schadet. Und sie wird mit einer einzigen Eingabe abgelehnt, bei der sie eine schlechtere Antwort liefert. Eine solche Eingabe heißt Gegenbeispiel. 6 Punkte sind ein Gegenbeispiel für gierig mit den Gutscheinen 4, 3 und 1.
Dieselbe Art Gutscheine kann je nach ihren Werten sicher oder unsicher sein. 4, 2 und 1 sind sicher: Jeder größere ist ein Vielfaches des kleineren. 4, 3 und 1 sind es nicht.
Sieh es dir an
Gierig und DP nebeneinander
Die Korrektur ist, nicht in einem Zug zu entscheiden, sondern die wenigsten Gutscheine für jeden Betrag von 0 bis 6 zu berechnen. Für p Punkte probierst du jeden Gutschein v als letzten: Es bleiben p − v Punkte, und die wenigsten dafür sind schon berechnet. Das ist dynamische Programmierung für Münzen, mit einer Tabelle best. last hält fest, welcher Gutschein zuletzt kam, damit du zu den Gutscheinen selbst zurückgehen kannst.
static List<Integer> fewest(int[] vouchers, int points) { int[] best = new int[points + 1]; int[] last = new int[points + 1]; for (int p = 1; p <= points; p++) { best[p] = points + 1; for (int v : vouchers) { if (v <= p && best[p - v] + 1 < best[p]) { best[p] = best[p - v] + 1; last[p] = v; } } } List<Integer> used = new ArrayList<>(); for (int p = points; p > 0; p -= last[p]) { used.add(last[p]); } return used;}int[] vouchers = {4, 3, 1};System.out.println("6 Punkte: gierig " + greedy(vouchers, 6) + ", am wenigsten " + fewest(vouchers, 6));System.out.println("10 Punkte: gierig " + greedy(vouchers, 10) + ", am wenigsten " + fewest(vouchers, 10));6 Punkte: gierig [4, 1, 1], am wenigsten [3, 3]10 Punkte: gierig [4, 4, 1, 1], am wenigsten [4, 3, 3]static List<Integer> fewest(int[] vouchers, int points) { int[] best = new int[points + 1]; int[] last = new int[points + 1]; for (int p = 1; p <= points; p++) { best[p] = points + 1; for (int v : vouchers) { if (v <= p && best[p - v] + 1 < best[p]) { best[p] = best[p - v] + 1; last[p] = v; } } } List<Integer> used = new ArrayList<>(); for (int p = points; p > 0; p -= last[p]) { used.add(last[p]); } return used;}static List<Integer> greedy(int[] vouchers, int points) { List<Integer> used = new ArrayList<>(); for (int v : vouchers) { while (points >= v) { used.add(v); points -= v; } } return used;}static List<Integer> fewest(int[] vouchers, int points) { int[] best = new int[points + 1]; int[] last = new int[points + 1]; for (int p = 1; p <= points; p++) { best[p] = points + 1; for (int v : vouchers) { if (v <= p && best[p - v] + 1 < best[p]) { best[p] = best[p - v] + 1; last[p] = v; } } } List<Integer> used = new ArrayList<>(); for (int p = points; p > 0; p -= last[p]) { used.add(last[p]); } return used;}Schritt für Schritt, in Worten
- Gierig, 6 Punkte. Der größte Gutschein, der passt, ist 4: Er nimmt ihn. Es bleiben 2 Punkte.
- Es bleiben 2 Punkte: 4 und 3 passen nicht. Er nimmt 1. Es bleiben 1 Punkt.
- Noch ein 1. Fertig: 4 + 1 + 1, 3 Gutscheine. Die Wahl von 4 war endgültig und verschloss den Weg zu 3 + 3.
- DP berechnet die wenigsten Gutscheine für jeden Betrag von 0 bis 6. best[0] = 0: 0 Punkte brauchen keinen Gutschein.
- best[1]: 1 → 1 + best[0] = 1. Am wenigsten 1, letzter Gutschein 1.
- best[2]: 1 → 1 + best[1] = 2. Am wenigsten 2, letzter Gutschein 1.
- best[3]: 3 → 1 + best[0] = 1; 1 → 1 + best[2] = 3. Am wenigsten 1, letzter Gutschein 3.
- best[4]: 4 → 1 + best[0] = 1; 3 → 1 + best[1] = 2; 1 → 1 + best[3] = 2. Am wenigsten 1, letzter Gutschein 4.
- best[5]: 4 → 1 + best[1] = 2; 3 → 1 + best[2] = 3; 1 → 1 + best[4] = 2. Am wenigsten 2, letzter Gutschein 4.
- best[6]: 4 → 1 + best[2] = 3; 3 → 1 + best[3] = 2; 1 → 1 + best[5] = 3. Am wenigsten 2, letzter Gutschein 3.
- Zurück entlang last: 6 → 3 → 0. Die Gutscheine sind 3 und 3: 2 Stück.
- Derselbe Betrag, zwei Antworten: Gierig liefert 3 Gutscheine, DP liefert 2. Gierig geht nie auf eine Wahl zurück; DP probiert für jeden Betrag jeden letzten Gutschein.
DP macht mehr Arbeit: Beträge × Gutscheine, also O(n·k), während gierig so lang ist wie die Gutscheine, die es nimmt. Aber DP ist für beliebige Gutscheine richtig, und gierig nur für manche.
„Unendlich“ in best ist points + 1: mehr als jede echte Antwort, weil bei einem Gutschein zu 1 Punkt die Antwort höchstens points ist. Integer.MAX_VALUE sieht natürlicher aus, aber best[p - v] + 1 würde zu -2.147.483.648 überlaufen und den Vergleich gewinnen.
Probier es aus
Sage voraus
Dieselben Gutscheine, 10 Punkte. Was liefert gierig?
static List<Integer> greedy(int[] vouchers, int points) { List<Integer> used = new ArrayList<>(); for (int v : vouchers) { while (points >= v) { used.add(v); points -= v; } } return used;}
int[] vouchers = {4, 3, 1};System.out.println(greedy(vouchers, 10));4 passt zweimal: 2 Punkte bleiben, und dann zwei Gutscheine zu 1 Punkt. Vier Gutscheine. Das Mindeste ist 4 + 3 + 3: drei. Auch 10 ist ein Gegenbeispiel.
Probier es aus
Ergänze
Für p Punkte mit v als letztem Gutschein: Aus welchem Betrag kommt der Rest?
static List<Integer> fewest(int[] vouchers, int points) {
int[] best = new int[points + 1];
int[] last = new int[points + 1];
for (int p = 1; p <= points; p++) {
best[p] = points + 1;
for (int v : vouchers) {
if (v <= p && best[p - v] + 1 < best[p]) {
best[p] = best[] + 1;
last[p] = v;
}
}
}
List<Integer> used = new ArrayList<>();
for (int p = points; p > 0; p -= last[p]) {
used.add(last[p]);
}
return used;
}Der Gutschein v deckt v Punkte, und es bleiben p - v. Die wenigsten dafür sind best[p - v], früher berechnet, weil p - v kleiner ist als p. Plus eins für v selbst.
Sieh es dir an
Das Rucksackproblem nach Gebühr pro Kilogramm
Der Kurier hat Platz für 10 kg. Drei Pakete warten: 6 kg mit einer Gebühr von 30 € und zwei zu 5 kg mit je 20 € Gebühr. Die gierige Idee: die Pakete nach Gebühr pro Kilogramm sortieren und nehmen, solange sie passen.
static int byRatio(int[][] parcels, int capacity) { int[][] sorted = parcels.clone(); Arrays.sort(sorted, (a, b) -> Double.compare((double) b[1] / b[0], (double) a[1] / a[0])); int total = 0; for (int[] p : sorted) { if (p[0] <= capacity) { capacity -= p[0]; total += p[1]; } } return total;}
static int bestFee(int[][] parcels, int i, int capacity) { if (i == parcels.length) { return 0; } int skip = bestFee(parcels, i + 1, capacity); if (parcels[i][0] > capacity) { return skip; } int take = parcels[i][1] + bestFee(parcels, i + 1, capacity - parcels[i][0]); return Math.max(skip, take);}int[][] parcels = {{6, 30}, {5, 20}, {5, 20}};System.out.println("Nach Gebühr pro Kilogramm: " + byRatio(parcels, 10) + " €");System.out.println("Am besten: " + bestFee(parcels, 0, 10) + " €");Nach Gebühr pro Kilogramm: 30 €Am besten: 40 €Das 6-kg-Paket bringt 5 € pro kg, die anderen 4 € pro kg. Gierig nimmt es zuerst, und die restlichen 4 kg reichen für nichts. Die zwei 5-kg-Pakete füllen den Transporter genau und bringen 40 €. bestFee probiert jede Teilmenge: Für jedes Paket „nehmen“ oder „auslassen“. Das ist 2ⁿ, und für eine echte Zahl von Paketen brauchst du DP für das Rucksackproblem.
(double) b[1] / b[0]: Ohne die Umwandlung in double ist die Division eine Ganzzahldivision, und 7 € für 2 kg werden zu 3 € pro kg statt 3,5. Dann stimmt die Reihenfolge schon, bevor gierig angefangen hat.Genauer, für Neugierige
Lassen sich die Pakete teilen, ist gierig nach Gebühr pro Kilogramm richtig. So funktioniert es bei loser Ware: Kaffeebohnen, Mehl, Treibstoff. Du nimmst so viel wie passt vom teuersten pro Kilogramm, dann vom nächsten, und schneidest das letzte ab. Das ist das fraktionale Rucksackproblem, und dort versperrt keine lokale Wahl einen besseren Weg.
Ein ganzes Paket lässt sich nicht zerschneiden. Genau das macht gierig gefährlich: Die 6 kg nehmen Platz weg, den die zwei 5-kg-Pakete besser nutzen würden.
Die Idee
Wie man eine gierige Idee testet
Eine gierige Idee klingt fast immer richtig. Wie findest du heraus, ob sie es ist? Du suchst ein Gegenbeispiel, nicht von Hand, sondern mit einem Programm:
- Schreibe eine langsame, aber sicher richtige Lösung: ein Brute Force, das jede Möglichkeit probiert.
- Lass gierig und das Brute Force auf allen kleinen Eingaben laufen: jeder Betrag von 1 bis 100.
- Die erste Stelle, an der sie sich unterscheiden, ist ein Gegenbeispiel. Stimmen sie überall überein, hast du nichts bewiesen, aber du hast einen Grund, einen Beweis zu suchen.
Das Brute Force hier probiert, wie viele von jeder Münze zu nehmen sind: von 0 bis so viele, wie passen, rekursiv für die nächste. Die letzte Münze ist 1, und sie deckt, was übrig bleibt.
static int tryAll(int[] coins, int i, int amount) { if (i == coins.length - 1) { return amount; } int best = Integer.MAX_VALUE; for (int k = 0; k * coins[i] <= amount; k++) { int rest = tryAll(coins, i + 1, amount - k * coins[i]); best = Math.min(best, k + rest); } return best;}
static void check(String name, int[] coins, int upTo) { for (int a = 1; a <= upTo; a++) { int g = greedy(coins, a).size(); int b = tryAll(coins, 0, a); if (g != b) { System.out.println(name + ": " + a + " → gierig " + g + ", am wenigsten " + b); return; } } System.out.println(name + ": bis " + upTo + " kein Gegenbeispiel");}check("Gutscheine 4, 3, 1", new int[] {4, 3, 1}, 20);check("Euro-Münzen", new int[] {200, 100, 50, 20, 10, 5, 2, 1}, 100);check("Alte britische", new int[] {30, 24, 12, 6, 3, 1}, 100);Gutscheine 4, 3, 1: 6 → gierig 3, am wenigsten 2Euro-Münzen: bis 100 kein GegenbeispielAlte britische: 48 → gierig 3, am wenigsten 2Drei Systeme in einer Sekunde:
- die Gutscheine 4, 3 und 1 fallen bei 6;
- die Euro-Münzen in Cent (1, 2, 5, 10, 20, 50 Cent, 1 € und 2 €) fallen bis 100 Cent nicht;
- die alten britischen Münzen in Pence (1, 3, 6, 12, 24 und 30, Teil des Systems vor 1971) fallen bei 48: Gierig liefert 30 + 12 + 6, während 24 + 24 zwei sind.
Das Brute Force ist exponentiell, und bei großen Eingaben ist es hoffnungslos. Aber Gegenbeispiele sind fast immer klein, und es geht durch kleine Eingaben im Nu.
Probier es aus
Finde den Fehler
Ein Kollege hat die Prüfung für die Gutscheine laufen lassen und verkündet, dass gierig richtig ist. Du weißt, dass 6 ein Gegenbeispiel ist. Wo steckt der Fehler?
check("Gutscheine 4, 3, 1", new int[] {4, 3, 1}, 5);check("Euro-Münzen", new int[] {200, 100, 50, 20, 10, 5, 2, 1}, 100);check("Alte britische", new int[] {30, 24, 12, 6, 3, 1}, 100);Gutscheine 4, 3, 1: bis 5 kein GegenbeispielEuro-Münzen: bis 100 kein GegenbeispielAlte britische: 48 → gierig 3, am wenigsten 2Wähle die Zeile mit dem Fehler.
Die Prüfung der Gutscheine geht nur bis 5 Punkte, und das erste Gegenbeispiel ist 6. Der Code stimmt, der Bereich nicht. Wie weit man gehen muss, sagt der Satz unter „Genauer“: bis zur Summe der zwei größten Werte, 4 + 3 = 7.
Genauer, für Neugierige
Wie weit prüfen. Für Münzen und Gutscheine gibt es eine genaue Antwort (Kozen und Zaks, 1994): Ist gierig irgendwo falsch, ist das kleinste Gegenbeispiel kleiner als die Summe der zwei größten Werte. Eine vollständige Prüfung bis dorthin ist also ein Beweis:
- die Gutscheine 4, 3 und 1: bis 7;
- die Euro-Münzen: bis 300 Cent (2 € + 1 €). Lass bis 300 laufen, die Prüfung findet kein Gegenbeispiel, also ist gierig für Euro-Münzen bei jedem Betrag richtig;
- die alten britischen Münzen: bis 54 (30 + 24), und 48 liegt unter dieser Grenze.
Euro-Münzen: bis 300 kein GegenbeispielBis 300 macht das Brute Force etwa 26 Millionen Aufrufe und ist trotzdem in Sekunden fertig. Für einen größeren Bereich ist die bessere Prüfung DP statt des Brute Force: Sie ist ebenso sicher richtig, und sie ist O(Betrag × Münzen).
Bei anderen Problemen gibt es meist keine solche Grenze. Dann beweist das Prüfen kleiner Eingaben nichts, es sucht nur. Der Beweis ist ein Argument: meist, dass sich jede optimale Lösung Schritt für Schritt in die gierige verwandeln lässt, ohne schlechter zu werden.
Übung
Die neuen Gutscheine des Marketings
Löse die Aufgabe in deinem Editor.
Die neuen Gutscheine. Das Marketing will Gutscheine zu 9, 6, 5 und 1 Punkt und fragt, ob die Kasse gierig bleiben kann. Nutze die Prüfung aus der Lektion (greedy, das Brute Force und check) für Beträge bis 30 Punkte und finde das kleinste Gegenbeispiel.
Gutscheine 9, 6, 5, 1: 11 → gierig 3, am wenigsten 2Weitere Aufgaben
- Das System korrigieren. Welchen Gutschein fügst du zu 4, 3 und 1 hinzu, damit gierig bis 7 richtig wird? Probiere es mit der Prüfung.
- Das Rucksackproblem mit Prüfung. Schreibe eine Prüfung für das Rucksackproblem: gierig nach Gebühr pro Kilogramm gegen
bestFeefür alle Kombinationen von drei Paketen mit Gewichten von 1 bis 6 kg und Gebühren von 1 € bis 9 €. Wie viele Gegenbeispiele findet sie? - Fristen. Die Aufgaben haben eine Dauer und eine Frist. Hält gierig „die kürzeste zuerst“ die meisten Fristen ein? Finde ein Gegenbeispiel, indem du jede Reihenfolge von 4 Aufgaben probierst.
Test