Das Wechselgeldproblem in JavaScript

Problem

Das Wechselgeld des Automaten

Der Parkautomat gibt Wechselgeld zurück. Er hat für jede der acht Euro-Münzen eine Röhre: 1, 2, 5, 10, 20 und 50 Cent, 1 € und 2 €. Je weniger Münzen er herausgibt, desto seltener muss jemand die Röhren nachfüllen. Das Wechselgeld soll also aus den wenigsten Münzen bestehen.

Der Entwickler will nicht raten und schreibt eine Rekursion, die alles ausprobiert: für jede Münze, die ins Wechselgeld passt, „diese Münze plus das Beste für den Rest“, und nimmt das Kleinste. Die Beträge sind in Cent, und der Zähler zählt die ausprobierten Münzen:

let tries = 0;

function fewest(coins, amount) {
  if (amount === 0) {
    return 0;
  }
  let best = amount + 1;
  for (const coin of coins) {
    if (coin > amount) {
      break;
    }
    tries++;
    const count = fewest(coins, amount - coin) + 1;
    best = Math.min(best, count);
  }
  return best;
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
for (const amount of [10, 20, 30]) {
  tries = 0;
  const count = fewest(coins, amount);
  console.log(`${amount} Cent: ${count} Münzen, ${tries} Versuche`);
}

10 Cent: 1 Münzen, 309 Versuche
20 Cent: 1 Münzen, 66281 Versuche
30 Cent: 2 Münzen, 14158888 Versuche

Die Antworten stimmen. Aber für 30 Cent probiert die Rekursion 14.158.888 Münzen aus, und für 40 Cent 3.024.560.419. Wechselgeld von 63 Cent braucht 689.951.222.249.236 Versuche: Bei einer Milliarde pro Sekunde sind das acht Tage, während der Fahrer an der Schranke wartet.

Die Idee

Die Tabelle

Die Rekursion fragt immer wieder dasselbe: das Beste für 13 Cent, für 8 Cent, für 3 Cent. Das sind die überlappenden Teilprobleme aus der vorigen Lektion. Nur gehen hier von jedem Betrag bis zu acht Zweige ab, einer für jede Münze, und der Baum wächst noch schneller.

Also bauen wir eine Tabelle von unten nach oben. Eine Tabelle der dynamischen Programmierung wird durch vier Dinge beschrieben:

Was die Zelle bedeutet. best[a] sind die wenigsten Münzen für genau a Cent.
Woher sie kommt. Die letzte Münze ist eine der passenden. Also ist best[a] gleich 1 + best[a − Münze] für die beste Münze.
In welcher Reihenfolge sie gefüllt wird. a − Münze ist kleiner als a. Von links nach rechts ist alles, was die Zelle liest, schon fertig.
Wo die Antwort steht. In der letzten Zelle, best[Wechselgeld]. Der Start ist best[0] = 0: Null Cent brauchen keine Münzen.

Das ist eine DP-Tabelle: eine Zelle für jedes Teilproblem, gefüllt in einer Reihenfolge, in der jede Zelle die Zellen, von denen sie abhängt, fertig vorfindet. Wie in der vorigen Lektion liegt die Wahl nur in der Zelle, zwischen mehreren Möglichkeiten.

Sieh es dir an

Zelle für Zelle

Die Tabelle für 9 Cent. Achte auf die Pfeile: Jeder kommt aus der Zelle a − Münze, und Zelle a behält das Kleinste, das sie gesehen hat:

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

Schritt für Schritt, in Worten

change(coins, 9): best[a] sind die wenigsten Münzen für a Cent, last[a] die Münze, mit der man dorthin kommt. best[0] = 0: Null Cent brauchen keine Münzen.
Probiere für jedes a von links nach rechts jede Münze bis a aus: eine Münze plus das Beste für den Rest, best[a − Münze] + 1. Der Pfeil kommt aus dieser Zelle.
a = 5: Die Münze 1 ergibt best[4] + 1 = 3, die Münze 2 ergibt best[3] + 1 = 3, die Münze 5 ergibt best[0] + 1 = 1. Die Zelle behält das Kleinste, und last merkt sich die Münze.
Die Münzen sind von klein nach groß geordnet, und 10 ist schon mehr als 9: Die Schleife hält dort an. Jede Zelle liest nur Zellen links von ihr, und die sind schon endgültig.
Zurück entlang last: 9 → 7 → 5 → 0. Die Münzen sind 2 + 2 + 5. 22 Versuche für 9 Cent, jede Zelle einmal gelöst.

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
console.log(change(coins, 9));

[ 2, 2, 5 ]

amount + 1 bedeutet „noch nichts“: Du brauchst nie mehr Münzen als Cent, denn schon Ein-Cent-Münzen ergeben genau amount. Der erste Versuch ist also immer besser.

Die Idee

Welche Münzen

Die Anzahl reicht nicht: Der Automat muss auch wissen, welche Münzen er ausgeben soll. Neben best[a] führt die Tabelle deshalb auch last[a], die Münze, die zum Besten für a führt. Am Ende beginnst du beim Wechselgeld: last[a] ausgeben, abziehen und wiederholen, bis du 0 erreichst.

let tries = 0;

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      tries++;
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
for (const amount of [63, 480]) {
  tries = 0;
  const used = change(coins, amount);
  console.log(`${amount} Cent: ${used.join(" + ")}, ${tries} Versuche`);
}

63 Cent: 1 + 2 + 10 + 50, 296 Versuche
480 Cent: 10 + 20 + 50 + 200 + 200, 3460 Versuche

296 Versuche für 63 Cent statt 689.951.222.249.236. Die Tabelle hat eine Zelle pro Cent, und jede Zelle probiert höchstens die acht Münzen aus. Die Arbeit ist O(n · k): n Cent mal k Münzarten. Mit k = 8 ist das linear im Wechselgeld.

Probier es aus

Ergänze

Eine Münze plus das Beste für den Rest. Welche Zelle liest der Versuch?

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      const count = best[] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

Die Idee

Warum nicht zuerst die größte Münze?

Ein Kassierer macht etwas anderes: Er gibt die größte Münze, die passt, und wiederholt das. Für 63 Cent sind das 50, 10, 2, 1: wieder vier Münzen. Mit Euro-Münzen liefert diese Regel immer die wenigsten Münzen. Die Münzen sind so gewählt.

Aber die Regel hängt vom Münzsystem ab. Bei anderen Münzen oder wenn eine Röhre im Automaten leer wird, kann „die größte zuerst“ mehr Münzen als nötig liefern. Wann sie funktioniert und wann sie scheitert, ist die Lektion „Wann ein gieriger Algorithmus scheitert“. Die Tabelle verlässt sich nicht darauf: Sie probiert für jeden Betrag jede Münze aus und findet die wenigsten für beliebige Münzen.

Die Idee

Auf wie viele Arten

Ein anderes Problem mit derselben Tabelle. Der Geldautomat zahlt Beträge in Scheinen zu 5, 10, 20 und 50 € aus. Die Tester wollen jede mögliche Kombination für 100 € prüfen und fragen: Wie viele gibt es?

Jetzt ist die Zelle count[a]: auf wie viele Arten sich genau a Euro bilden lassen. count[0] = 1, die leere Kombination. Die äußere Schleife geht über die Scheine, die innere über die Beträge:

function ways(notes, amount) {
  const count = new Array(amount + 1).fill(0);
  count[0] = 1;
  for (const note of notes) {
    for (let a = note; a <= amount; a++) {
      count[a] += count[a - note];
    }
  }
  return count[amount];
}

const notes = [5, 10, 20, 50];
console.log(ways(notes, 100), "Möglichkeiten");

49 Möglichkeiten

Die Reihenfolge der Schleifen ist wichtig. Wenn die Fünfer ganz vor den Zehnern kommen, wird jede Kombination in einer Reihenfolge gebaut: erst die Fünfer, dann die Zehner. 5 + 10 und 10 + 5 sind also dieselbe Kombination und werden einmal gezählt. Und hier sucht niemand ein Minimum: Die Zelle addiert die Anzahl der Möglichkeiten aus den Zellen links von ihr.

Probier es aus

Sag die Ausgabe voraus

Wie viele Kombinationen gibt es für 20 € mit Scheinen zu 5, 10 und 20?

function ways(notes, amount) {
  const count = new Array(amount + 1).fill(0);
  count[0] = 1;
  for (const note of notes) {
    for (let a = note; a <= amount; a++) {
      count[a] += count[a - note];
    }
  }
  return count[amount];
}

const notes = [5, 10, 20];
console.log(ways(notes, 20), "Möglichkeiten");

Antwort

3 Möglichkeiten

4 Möglichkeiten

6 Möglichkeiten

Probier es aus

Finde den Fehler

Ein Kollege hat dieselbe Zählung geschrieben, aber für 100 € kommt eine viel größere Zahl heraus:

const notes = [5, 10, 20, 50];
console.log(ways(notes, 100), "Möglichkeiten");

48007 Möglichkeiten

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Sieh es dir an

Miss es: Rekursion gegen Tabelle

Wir zählen die ausprobierten Münzen: in jedem rekursiven Aufruf und in jeder Zelle. Die Rekursion wird über 30 Cent nicht ausgeführt: Bei 40 Cent sind es über 3 Milliarden Versuche.

Rekursion ohne Gedächtnis O(2ⁿ)
Tabelle O(n)

Algorithmus	n = 10	n = 20	n = 30
Rekursion ohne Gedächtnis	309	66.281	14.158.888
Tabelle	26	67	117

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

Alle 10 Cent vervielfacht sich die Rekursion um etwa das 200-Fache, während die Tabelle um 40 bis 50 Versuche wächst. Die Kurve der Rekursion ist mit O(2ⁿ) beschriftet: Sie ist exponentiell, mit einer Basis von etwa 1,7.

Genauer, für Neugierige

Dieselben Zahlen in deiner Sprache:

let tries = 0;

function fewest(coins, amount) {
  if (amount === 0) {
    return 0;
  }
  let best = amount + 1;
  for (const coin of coins) {
    if (coin > amount) {
      break;
    }
    tries++;
    const count = fewest(coins, amount - coin) + 1;
    best = Math.min(best, count);
  }
  return best;
}

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      tries++;
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
for (const amount of [10, 20, 30]) {
  tries = 0;
  fewest(coins, amount);
  const plain = tries;
  tries = 0;
  change(coins, amount);
  console.log(`${amount} Cent: ohne Speicher ${plain}, Tabelle ${tries}`);
}

10 Cent: ohne Speicher 309, Tabelle 26
20 Cent: ohne Speicher 66281, Tabelle 67
30 Cent: ohne Speicher 14158888, Tabelle 117

Übung

Das Wechselgeld aus der Eingabe

Löse die Aufgabe in deinem Editor.

Wechselgeld. Lies das Wechselgeld in Cent ein und gib aus, wie viele Münzen der Automat herausgibt und welche. Nutze change aus der Lektion.

5 Münzen: 10 + 20 + 50 + 200 + 200

Weitere Aufgaben

Eine leere Röhre. Die Röhren für 1 und 2 Cent sind leer. Welche Beträge unter 1 € kann der Automat gar nicht zurückgeben? Woran erkennst du es in der Tabelle? (Tipp: Die Zelle bleibt amount + 1.)
Die größte zuerst. Gib die Münzen von der größten zur kleinsten aus.
Wie viele Arten mit Münzen. Auf wie viele Arten kannst du 1 € mit den Münzen von 1 bis 50 Cent zahlen? Und wenn die 1-€-Münze auch erlaubt ist?

Genauer

Unmögliches Wechselgeld und sehr große Zahlen

Zwei Dinge, die die Lektion übersprungen hat.

Genauer, für Neugierige

Wenn das Wechselgeld nicht zurückgegeben werden kann. Wenn die Röhren für 1 und 2 Cent leer sind, lassen sich 3 Cent mit nichts zurückgeben. Dann bleibt die Zelle amount + 1, weil kein Versuch besser ist. Und wenn last[a] 0 ist, würde der Weg zurück ewig auf der Stelle drehen. Vor dem Zurückgehen prüfst du also, ob best[amount] > amount gilt, und der Automat sagt „Kein Wechselgeld, bitte zahlen Sie passend“.

Die Zahl der Möglichkeiten wächst sehr schnell. Auf wie viele Arten kannst du 100 € nur mit Münzen zahlen (10.000 Cent, die acht Euro-Münzen)?

function ways(notes, amount) {
  const count = new Array(amount + 1).fill(0);
  count[0] = 1;
  for (const note of notes) {
    for (let a = note; a <= amount; a++) {
      count[a] += count[a - note];
    }
  }
  return count[amount];
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
console.log(ways(coins, 10000));

1133873304647601

In JavaScript ist eine Zahl ein Gleitkommawert und hält ganze Zahlen bis 2⁵³ exakt, etwa 9 · 10¹⁵. Diese Zahl liegt darunter und ist exakt. Bei größeren Beträgen müssen die Zellen BigInt sein (0n, 1n), sonst wird die Antwort stillschweigend gerundet.

Die Tabelle in zwei Dimensionen. Das Zählen der Möglichkeiten ist eigentlich eine Tabelle „die ersten i Scheine × der Betrag“: Zelle (i, a) sagt, auf wie viele Arten sich a nur mit den ersten i Scheinen bilden lässt. Zeile i entsteht aus der Zeile darüber (ohne Schein i) und aus der Zelle links in derselben Zeile (mit einem weiteren Schein i). Das Programm behält nur eine Zeile und überschreibt sie von links nach rechts. Deshalb geht die äußere Schleife über die Scheine: Sie läuft durch die Zeilen. Dieselbe Idee, eine Zeile statt der ganzen Tabelle, kehrt im Rucksackproblem wieder.

Test

Teste dich

1. Was bedeutet die Zelle best[a] in der Wechselgeld-Tabelle?Wie viele Münzen vom Wert a der Automat hatDie wenigsten Münzen, die genau a Cent ergebenDie größte Münze, die in a passt

2. Warum wird die Tabelle von links nach rechts gefüllt, ab a = 1?Zelle a liest nur Zellen a − Münze, die links von ihr liegen und schon endgültig sindDie Reihenfolge ist egal, von rechts nach links geht es auchWeil die Münzen von links nach rechts geordnet sind

3. Wie sagt die Tabelle, welche Münzen es sind und nicht nur wie viele?last[a] merkt sich die Münze, die zum Besten für a führt; wer vom Wechselgeld an last entlang zurückgeht, bekommt die Münzen eine nach der anderenSie zählt, wie oft jede Zelle benutzt wurdeGar nicht: Dafür braucht man für jede Münze eine zweite Tabelle

4. Beim Zählen der Möglichkeiten sind die Schleifen vertauscht: Die äußere geht über die Beträge, die innere über die Scheine. Was passiert?Nichts, das Ergebnis ist dasselbeEs zählt weniger MöglichkeitenEs zählt Reihenfolgen: 5 + 10 und 10 + 5 werden zwei Möglichkeiten, die Zahl ist also viel größer

5. Mit Euro-Münzen liefert „die größte Münze, die passt, und wieder von vorn“ die wenigsten Münzen. Wozu also eine Tabelle?Die Tabelle liefert die wenigsten Münzen für beliebige Münzen, während die gierige Regel Münzsysteme hat, bei denen sie falsch liegtDie Tabelle ist schneller als die gierige RegelDie gierige Regel funktioniert bei Euro-Münzen nicht

Das Wechselgeldproblem

Cookies