Münzwechsel: Greedy gegen optimal

Gib Münzwerte und einen Betrag ein. Die Seite stellt den Betrag auf zwei Arten zusammen: Beim Greedy-Verfahren wird jeweils die größte noch passende Münze genommen, bis kein Rest mehr bleibt oder keine Münze mehr passt. Daneben wird mithilfe einer Tabelle, die von 0 bis zum Betrag gefüllt wird, die Lösung mit möglichst wenigen Münzen ermittelt. Unter der Tabelle siehst du alle Beträge bis zu einer von dir gewählten Grenze; markiert sind jene, für die das Greedy-Verfahren mehr Münzen verwendet als nötig.

Rechenbeispiel — Münzwechsel: Greedy gegen optimal

Greedy, größte Münze zuerst	3 Münzen
Kleinste Münzzahl aus der Tabelle	2 Münzen: 2×24
Hier von Greedy verschwendete Münzen	1
Beträge von 1 bis 240, bei denen Greedy verliert	42 von 240
Kleinster Betrag, bei dem Greedy verliert	48

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Münzwechsel: Greedy gegen optimal

Das Münzwechselproblem fragt nach der kleinsten Anzahl von Münzen aus einem vorgegebenen Münzsatz, die zusammen einen Betrag ergeben. Jede Münze darf beliebig oft verwendet werden. Der Greedy-Algorithmus nimmt jeweils die größte passende Münze und wiederholt diesen Schritt. Dynamische Programmierung löst das Problem exakt, indem sie zunächst alle kleineren Beträge löst: M(0) = 0 und M(a) = 1 + min M(a − c) über alle Münzen c ≤ a. Ein Münzsystem, in dem Greedy für jeden Betrag optimal ist, heißt kanonisch.

Was die einzelnen Symbole bedeuten

M(a): die kleinste Münzzahl für den Betrag a; die Zahl in Zelle a der Tabelle
G(a): die Anzahl der Münzen, die Greedy für a verwendet
cₘ, cₘ₋₁: die größte und die zweitgrößte Münze; gibt es einen Betrag, bei dem Greedy erstmals verliert, ist er kleiner als ihre Summe

Setzt voraus: Von jeder ganzzahligen Münzsorte steht eine unbegrenzte Menge bereit, und allein die Anzahl der Münzen zählt. Eine Kasse, der die Florins ausgegangen sind, stellt ein anderes Problem. Für die Schranke muss der Münzsatz eine 1 enthalten. Ohne sie sind manche Beträge überhaupt nicht zahlbar, und Greedy kann vor einem Betrag stecken bleiben, den die Tabelle zahlen kann.

Beim alten britischen Geld verlor Greedy bei vier Shilling 🖖

Drück auf GB vor 1971. Um 48d, also vier Shilling, zu zahlen, nimmt Greedy zuerst die größte passende Münze: eine Half Crown (30d), dann einen Shilling (12d) und eine Sixpence (6d), insgesamt drei Münzen. Zwei Florins zu je 24d ergeben dieselben 48d mit zwei Münzen. Von da an verliert Greedy bei sechs Beträgen je dreißig Pence: 48–53d, 78–83d und so weiter bis 228–233d. Das sind 42 der 240 Beträge in einem Pfund. Jedes Mal kostet Greedy genau eine Münze mehr, deshalb sind alle roten Balken im Streifen gleich hoch. Die sechs Beträge lassen nach einer oder mehreren Half Crowns einen Rest von 18 bis 23 Pence. Nimm eine Half Crown zurück und zahle 48d mit zwei Florins, dann sparst du eine Münze. Auch der Halfpenny hilft nicht. Gib die Münzen in Halfpence ein, 1, 2, 6, 12, 24, 48, 60, und prüfe bis 480. Das erste Gegenbeispiel liegt bei 96 Halfpence, weiterhin 48d. Greedy verliert bei 84 der 480 Beträge: bei denselben 42 und jeweils beim halben Penny darüber.

Ohne die Half Crown scheitert Greedy nie 🖖

Drück auf Ohne Half Crown. Es sind dieselben Münzen bis auf eine: 1, 3, 6, 12 und 24 Pence. Der Streifen bleibt leer, denn Greedy verliert bei keinem der 240 Beträge. Jede dieser Münzen teilt die nächstgrößere. In einer solchen Kette kann Greedy nicht verlieren: Sobald genügend gleiche Münzen den Wert der nächstgrößeren erreichen, lassen sie sich durch diese eine Münze ersetzen. Die Half Crown unterbricht die Kette. Dreißig ist kein Vielfaches von vierundzwanzig. Zwei Florins entsprechen einer Half Crown plus 18d, wofür ein Shilling und eine Sixpence nötig sind. Jedes Gegenbeispiel im ersten Streifen beruht auf genau diesem Tausch. Eine weitere Münze löst das Problem ebenfalls nicht. Gib 1, 3, 6, 12, 24, 30, 60 ein, um die Crown zu fünf Shilling hinzuzufügen. Die Zahl der Gegenbeispiele sinkt von 42 auf 24, doch 48d bleibt das erste. Bei Beträgen unter ihrem eigenen Wert kann eine Crown schließlich nichts ausrichten.

Ein Münzsystem lässt sich in endlich vielen Schritten prüfen 🖖

Dass Greedy bei 48d scheitert, sagt zunächst nichts über 4.800d aus. Ein Satz von Dexter Kozen und Shmuel Zaks aus dem Jahr 1994 entscheidet ein System für sämtliche Beträge: Enthält der Münzsatz eine 1 und verliert Greedy irgendwo, dann liegt der kleinste Gegenbeleg echt zwischen c₃ + 1 und c_m + c_m−1. Dabei ist c₃ die drittkleinste Münze; c_m und c_m−1 sind die beiden größten. Drück auf US-Cent. Die beiden größten Münzen haben die Werte 100 und 50. Unter 150 gibt es kein Gegenbeispiel, und diese endliche Prüfung deckt damit alle denkbaren Beträge ab. Beim Euro reicht sie bis 300. Enger lässt sich die Schranke nicht fassen. Drück auf Lehrbuch: 1, 3, 4: Zwischen 5 und 7 liegt genau ein Betrag, nämlich 6, und genau dort verliert Greedy. Die gestrichelte Linie im Streifen markiert die Schranke. Enthält der Münzsatz eine 1, liegt der erste rote Balken stets links davon.

Aufgabe vollständig gelöst

Welche dritte Münze passt zu 1 und 5? 3 Schritte
Ein Land hat Münzen zu 1 und 5 und möchte eine dritte Münze d zwischen 6 und 30 einführen. Für welche Werte von d liefert Greedy immer optimales Wechselgeld? Die Seite prüft jeweils nur ein System. Die Regel von Kozen und Zaks für drei Münzen entscheidet jedoch alle 25 auf einmal. Drück zuerst auf Lehrbuch: 1, 3, 4, um die Regel an einem bereits geprüften System auszuprobieren.

Öffne diese Aufgabe im Tool
1. Die Regel für Münzen 1 < c < d lautet: Schreibe d = qc + r mit 0 ≤ r < c. Das System scheitert genau dann irgendwo, wenn 0 < r < c − q gilt. Für 1, 3, 4 ist d = 4 = 1 × 3 + 1, also q = 1 und r = 1. Damit gilt 0 < 1 < 2. Das System scheitert, und die Seite findet das erste Gegenbeispiel bei 6:
  
  $4 = 1 \times 3 + 1 : q = 1, r = 1, 0 < 1 < 3 - 1 = 2$
2. Nun ist c = 5, also d = 5q + r. Zu prüfen ist 0 < r < 5 − q. Je größer q wird, desto weniger Spielraum bleibt für r:
  
  $d = 5 q + r, 0 \leq r < 5 : 0 < r < 5 - q$
3. Für q = 1 (d von 6 bis 9) kann r gleich 1, 2 oder 3 sein. Damit scheitern d = 6, 7 und 8. Für q = 2 (10 bis 14) kommen r = 1 oder 2 infrage: 11 und 12. Für q = 3 (15 bis 19) bleibt nur r = 1, also 16. Ab q = 4 ist 5 − q höchstens 1, sodass kein r mehr passt:
  
  $q = 1 : d \in {6, 7, 8} q = 2 : d \in {11, 12} q = 3 : d = 16 q \geq 4 : 5 - q \leq 1$
Antwort

Sechs Werte scheitern: 6, 7, 8, 11, 12 und 16. Die übrigen neunzehn funktionieren, darunter jedes d von 17 bis 30. Gib 1, 5, 12 ein, um eines der sechs Beispiele zu verfolgen. Greedy zahlt 15 als 12 + 1 + 1 + 1 mit vier Münzen; drei Fünfer genügen.

$d \in {6, 7, 8, 11, 12, 16} 15 = 12 + 1 + 1 + 1 = 5 + 5 + 5$

Lernpfad

Warum ein Algorithmus korrekt ist

Quellen (3)

The bound the page draws as a dashed line and settles every system with: if greedy is ever beaten, the smallest amount where it is beaten lies strictly between c₃ + 1 and cₘ + cₘ₋₁; the three-coin rule the worked problem uses; the {1, 3, 4} example and the US system 1, 5, 10, 25, 50, 100 as canonical: D. Kozen and S. Zaks, "Optimal bounds for the change-making problem." Theoretical Computer Science 123(2), 1994, pp. 377-388. DOI 10.1016/0304-3975(94)90134-1
The pre-decimal coins and their values in pence (threepence, sixpence, shilling of 12d, florin of two shillings, half-crown of two shillings and sixpence, crown of five shillings), and the halfpenny's end as legal tender on 31 July 1969: Wikipedia contributors, "£sd", Wikipedia, The Free Encyclopedia, accessed 3 October 2026.
Which coins made up the circulating set at the end, as the Royal Mint itself issued them in 1970: half-crown, florin, shilling, sixpence, threepence, penny and halfpenny: The Royal Mint, "1970 Pre-Decimal UK Proof Set", product description, accessed 3 October 2026.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.