Das Münzwechselproblem

Auf dieser Seite wird das Münzwechselproblem NICHT behandelt.

Beispiel

Als Beispiel nehmen wir die Herausgabe von Wechselgeld auf Beträge unter 1€. Verfügbar sind die Münzen mit den Werten 50ct, 10ct, 5ct, 2ct, 1ct. Unser Ziel ist, so wenig Münzen wie möglich in das Portemonnaie zu bekommen.

Ein Beispiel: $78 c t = 50 + 2 \cdot 10 + 5 + 2 + 1$

Es wird jeweils immer die größte Münze unter dem Zielwert genommen und von diesem abgezogen. Das wird so lange durchgeführt, bis der Zielwert Null ist.

Formalisierung

Gesucht ist ein Algorithmus der folgende Eigenschaften beschreibt.

Bei der Eingabe muss gelten

1. dass die eingegebene Zahl eine natürliche Zahl ist, also

a m o u n t > 0

2. dass eine Menge von Münzwerten zur Verfügung steht

c u r r e n c y = {c_{1}, ..., c_{n}} z.B. {1, 2, 5, 10, 20, 50}

Die Ausgabe besteht dann aus ganzen Zahlen $c h a n g e [1], ..., c h a n g e [n]$ . Dabei ist $c h a n g e [i]$ die Anzahl der Münzen des Münzwertes für $c_{i}$ für $i = 1, ..., n$ und haben die Eigenschaften

1.

c h a n g e [1] \cdot c_{1} + ... + c h a n g e [n] \cdot c_{n} = a m o u n t

2.

c h a n g e [1] + ... + c h a n g e [n]

ist minimal unter allen Lösungen für 1.

Algorithmus

1. Nehme jeweils immer die größte Münze unter dem Zielwert und ziehe sie von diesem ab.

2. Verfahre derart, bis der Zielwert gleich Null ist.

Der dazugehörige Code in Java:

public int[] moneyChange(int[] currency, int amount){
   int[] change = new int[currency.length];
   int currentCoin = currency.length-1;
   while(amount > 0){
      while(amount < currency[currentCoin] && currentCoin > 0)
         currentCoin--;
      if(amount >= currency[currentCoin] && currentCoin >= 0){
         amount -= currency[currentCoin];
         change[currentCoin]++;
      } else return null;
   }
   return change;
}

Die Methode moneyChange wird dabei aufgerufen durch:

int[] currency = {1,2,5,10,20,50};
int amount = 78;
int[] change = moneyChange(currency, amount);

Lokales Optimum

Der Greedy Algorithmus berechnet im jedem Schritt das lokale Optimum, dabei kann jedoch das globale Optimum verfehlt werden.

Beispiel: Münzen 11ct, 5ct und 1ct. Unser Zielwert ist 15ct. Nach Greedy benutzen wir 11+1+1+1+1, das Optimum wäre aber 5+5+5.

Analyse

Theorem

Für $c u r r e n c y$ endlicher Länge und mit endlichen positiven Werten und endlichem positivem $a m o u n t$ , terminiert der Algorithmus moneyChange nach endlich viele Schritten.

Beweis

In Zeile 03 wird $c u r r e n t C o i n$ mit einem endlichen positiven Wert initialisiert
In Zeile 05 und 06 wird $c u r r e n t C o i n$ nur dekrementiert, spätestens beim Wert 0 wird die Schleife beendet (also eine endliche Wiederholung)
Falls die Zeilen 08 und 09 nicht ausgeführt werden, endet die Berechnung direkt in 10; andernfalls wird $a m o u n t$ in Zeile 08 echt kleiner
Irgendwann ist also der Bedingung in Zeile 04 nicht mehr gegeben und die Berechnung terminiert

Theorem

Für Eingabe $c u r r e n c y$ mit $| c u r r e n c y | = m$ und $a m o u n t = n$ hat der Algorithmus moneyChange eine Laufzeit von O(m+n).

Beweis

Die Zeile 6 wird maximal m-mal ausgeführt
Die Zeile 8 wird maximal n-mal ausgeführt, falls es nur eine Münze mit dem Wert "1" gibt

Theorem

Der Algorithmus moneyChange löst für $c u r r e n c y = {1, 2, 5, 10, 20, 50}$ das Münzwechselproblem.

Beweis

Bei der Lösung musste zum Einen gelten, dass $c h a n g e [1] \cdot c_{1} + ... + c h a n g e [n] \cdot c_{n} = a m o u n t$ ist. Da der Wert $a m o u n t$ stets um den Wert einer Münze $c_{i}$ verringert wird, während $c h a n g e [i]$ um eins inkrementiert wird, ist dies erfüllt.

Die zweite Aussage zur Lösung war, dass $c h a n g e [1] + ... + c h a n g e [n]$ minimal unter allen Lösungen sein soll. Dies wird hier nur für Münzen vom Wert 1,2 und 5 betrachtet, wobei es für die Münzen 10, 20 und 50 analog zu beweisen ist.

Zunächst gilt, dass 2er-Münzen stets 1er-Münzen zu bevorzugen sind, da es keinen Sinn macht im Algorithmus auf eine 2er-Münze zu verzichten, um dann im nächsten Schritt mehr 1er-Münzen zu bekommen. Das bedeutet, dass eine optimale Lösung maximal eine 1er-Münze beinhaltet.

Weiterhin gilt, eine optimale Lösung hat nicht mehr als zwei 2er-Münzen. Sollten drei 2er-Münzen in der Lösung sein, ist es besser diese durch eine 1er und eine 5er-Münze zu ersetzen.

Des Weiteren gilt, eine optimale Lösung kann nicht gleichzeitig eine 1er-Münze und zwei 2er-Münzen enthalten, weil dies durch eine 5er-Münze dargestellt werden kann.

Es folgt, dass der durch 1er- und 2er-Münzen dargestellte Betrag nicht mehr als 4 sein kann. Also ist eine maximale Wahl von 5er-Münzen im Greedy-Verfahren optimal.