Zum Inhalt
wannacode

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.

function greedy(vouchers, points) {
  const used = [];
  for (const v of vouchers) {
    while (points >= v) {
      used.push(v);
      points -= v;
    }
  }
  return used;
}
const vouchers = [4, 3, 1];
console.log("6 Punkte: " + "[" + greedy(vouchers, 6).join(", ") + "]");
Ausgabe
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.

function fewest(vouchers, points) {
  const best = [0];
  const last = [0];
  for (let p = 1; p <= points; p++) {
    best[p] = points + 1;
    last[p] = 0;
    for (const v of vouchers) {
      if (v <= p && best[p - v] + 1 < best[p]) {
        best[p] = best[p - v] + 1;
        last[p] = v;
      }
    }
  }
  const used = [];
  for (let p = points; p > 0; p -= last[p]) {
    used.push(last[p]);
  }
  return used;
}
const vouchers = [4, 3, 1];
console.log("6 Punkte: gierig " + "[" + greedy(vouchers, 6).join(", ") + "]" + ", am wenigsten " + "[" + fewest(vouchers, 6).join(", ") + "]");
console.log("10 Punkte: gierig " + "[" + greedy(vouchers, 10).join(", ") + "]" + ", am wenigsten " + "[" + fewest(vouchers, 10).join(", ") + "]");
Ausgabe
6 Punkte: gierig [4, 1, 1], am wenigsten [3, 3]
10 Punkte: gierig [4, 4, 1, 1], am wenigsten [4, 3, 3]

function fewest(vouchers, points) {
  const best = [0];
  const last = [0];
  for (let p = 1; p <= points; p++) {
    best[p] = points + 1;
    last[p] = 0;
    for (const v of vouchers) {
      if (v <= p && best[p - v] + 1 < best[p]) {
        best[p] = best[p - v] + 1;
        last[p] = v;
      }
    }
  }
  const used = [];
  for (let p = points; p > 0; p -= last[p]) {
    used.push(last[p]);
  }
  return used;
}
Schritt für Schritt, in Worten
  1. Gierig, 6 Punkte. Der größte Gutschein, der passt, ist 4: Er nimmt ihn. Es bleiben 2 Punkte.
  2. Es bleiben 2 Punkte: 4 und 3 passen nicht. Er nimmt 1. Es bleiben 1 Punkt.
  3. Noch ein 1. Fertig: 4 + 1 + 1, 3 Gutscheine. Die Wahl von 4 war endgültig und verschloss den Weg zu 3 + 3.
  4. DP berechnet die wenigsten Gutscheine für jeden Betrag von 0 bis 6. best[0] = 0: 0 Punkte brauchen keinen Gutschein.
  5. best[1]: 1 → 1 + best[0] = 1. Am wenigsten 1, letzter Gutschein 1.
  6. best[2]: 1 → 1 + best[1] = 2. Am wenigsten 2, letzter Gutschein 1.
  7. best[3]: 3 → 1 + best[0] = 1; 1 → 1 + best[2] = 3. Am wenigsten 1, letzter Gutschein 3.
  8. best[4]: 4 → 1 + best[0] = 1; 3 → 1 + best[1] = 2; 1 → 1 + best[3] = 2. Am wenigsten 1, letzter Gutschein 4.
  9. best[5]: 4 → 1 + best[1] = 2; 3 → 1 + best[2] = 3; 1 → 1 + best[4] = 2. Am wenigsten 2, letzter Gutschein 4.
  10. best[6]: 4 → 1 + best[2] = 3; 3 → 1 + best[3] = 2; 1 → 1 + best[5] = 3. Am wenigsten 2, letzter Gutschein 3.
  11. Zurück entlang last: 6 → 3 → 0. Die Gutscheine sind 3 und 3: 2 Stück.
  12. 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. In JavaScript funktioniert auch Infinity: Infinity + 1 ist weiterhin Infinity. In Java und C# läuft MAX_VALUE + 1 zu einer negativen Zahl über, also ist dort points + 1 ein Muss, hier eine Wahl.

Probier es aus

Sage voraus

Dieselben Gutscheine, 10 Punkte. Was liefert gierig?

function greedy(vouchers, points) {
  const used = [];
  for (const v of vouchers) {
    while (points >= v) {
      used.push(v);
      points -= v;
    }
  }
  return used;
}


const vouchers = [4, 3, 1];
console.log("[" + greedy(vouchers, 10).join(", ") + "]");
Antwort

Probier es aus

Ergänze

Für p Punkte mit v als letztem Gutschein: Aus welchem Betrag kommt der Rest?

function fewest(vouchers, points) {
  const best = [0];
  const last = [0];
  for (let p = 1; p <= points; p++) {
    best[p] = points + 1;
    last[p] = 0;
    for (const v of vouchers) {
      if (v <= p && best[p - v] + 1 < best[p]) {
        best[p] = best[] + 1;
        last[p] = v;
      }
    }
  }
  const used = [];
  for (let p = points; p > 0; p -= last[p]) {
    used.push(last[p]);
  }
  return used;
}

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.

function byRatio(parcels, capacity) {
  const sorted = [...parcels].sort((a, b) => b[1] / b[0] - a[1] / a[0]);
  let total = 0;
  for (const [kg, fee] of sorted) {
    if (kg <= capacity) {
      capacity -= kg;
      total += fee;
    }
  }
  return total;
}


function bestFee(parcels, i, capacity) {
  if (i === parcels.length) {
    return 0;
  }
  const skip = bestFee(parcels, i + 1, capacity);
  const [kg, fee] = parcels[i];
  if (kg > capacity) {
    return skip;
  }
  const take = fee + bestFee(parcels, i + 1, capacity - kg);
  return Math.max(skip, take);
}
const parcels = [[6, 30], [5, 20], [5, 20]];
console.log(`Nach Gebühr pro Kilogramm: ${byRatio(parcels, 10)} €`);
console.log(`Am besten: ${bestFee(parcels, 0, 10)} €`);
Ausgabe
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.

b[1] / b[0] liefert in JavaScript immer eine Bruchzahl. In Java und C# ist die Division zweier ganzer Zahlen eine Ganzzahldivision, und dort braucht man (double).
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:

  1. Schreibe eine langsame, aber sicher richtige Lösung: ein Brute Force, das jede Möglichkeit probiert.
  2. Lass gierig und das Brute Force auf allen kleinen Eingaben laufen: jeder Betrag von 1 bis 100.
  3. 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.

function tryAll(coins, i, amount) {
  if (i === coins.length - 1) {
    return amount;
  }
  let best = Infinity;
  for (let k = 0; k * coins[i] <= amount; k++) {
    const rest = tryAll(coins, i + 1, amount - k * coins[i]);
    best = Math.min(best, k + rest);
  }
  return best;
}


function check(name, coins, upTo) {
  for (let a = 1; a <= upTo; a++) {
    const g = greedy(coins, a).length;
    const b = tryAll(coins, 0, a);
    if (g !== b) {
      console.log(`${name}: ${a} → gierig ${g}, am wenigsten ${b}`);
      return;
    }
  }
  console.log(`${name}: bis ${upTo} kein Gegenbeispiel`);
}
check("Gutscheine 4, 3, 1", [4, 3, 1], 20);
check("Euro-Münzen", [200, 100, 50, 20, 10, 5, 2, 1], 100);
check("Alte britische", [30, 24, 12, 6, 3, 1], 100);
Ausgabe
Gutscheine 4, 3, 1: 6 → gierig 3, am wenigsten 2
Euro-Münzen: bis 100 kein Gegenbeispiel
Alte britische: 48 → gierig 3, am wenigsten 2

Drei 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", [4, 3, 1], 5);
check("Euro-Münzen", [200, 100, 50, 20, 10, 5, 2, 1], 100);
check("Alte britische", [30, 24, 12, 6, 3, 1], 100);
Ausgabe
Gutscheine 4, 3, 1: bis 5 kein Gegenbeispiel
Euro-Münzen: bis 100 kein Gegenbeispiel
Alte britische: 48 → gierig 3, am wenigsten 2

Wähle die Zeile mit dem Fehler.

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 Cent
Euro-Münzen: bis 300 kein Gegenbeispiel

Bis 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.

Ausgabe
Gutscheine 9, 6, 5, 1: 11 → gierig 3, am wenigsten 2

Weitere 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 bestFee fü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

Teste dich

1. Die Gutscheine sind 4, 3 und 1 Punkt. Wie viele Gutscheine liefert gierig für 6 Punkte, und was ist das Mindeste?
2. Eine gierige Idee hat 50 Tests bestanden. Was beweist das?
3. Der Kurier hat Platz für 10 kg. Pakete: 6 kg für 30 €, 5 kg für 20 € und 5 kg für 20 €. Was nimmt gierig nach Gebühr pro Kilogramm?
4. Warum ist „unendlich“ im DP der Gutscheine points + 1 und nicht Integer.MAX_VALUE in Java?
5. Die Prüfung sucht ein Gegenbeispiel für die Gutscheine 4, 3 und 1 nur bis 5 Punkte und findet keins. Warum?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·