Das Münzwechselproblem[Bearbeiten]

Auf dieser Seite wird das Münzwechselproblem NICHT behandelt.

Beispiel[Bearbeiten]

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: $78ct=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[Bearbeiten]

Gesucht ist ein Algorithmus der folgende Eigenschaften beschreibt.

Bei der Eingabe muss gelten

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

amount>0

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

currency=\{c_{1},...,c_{n}\}\ {\text{z.B.}}\{1,2,5,10,20,50\}

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

1.

change[1]\cdot c_{1}+...+change[n]\cdot c_{n}=amount

2.

change[1]+...+change[n]

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

Algorithmus[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Theorem[Bearbeiten]

Für $currency$ endlicher Länge und mit endlichen positiven Werten und endlichem positivem $amount$ , terminiert der Algorithmus moneyChange nach endlich viele Schritten.

Beweis[Bearbeiten]

In Zeile 03 wird $currentCoin$ mit einem endlichen positiven Wert initialisiert
In Zeile 05 und 06 wird $currentCoin$ 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 $amount$ in Zeile 08 echt kleiner
Irgendwann ist also der Bedingung in Zeile 04 nicht mehr gegeben und die Berechnung terminiert

Theorem[Bearbeiten]

Für Eingabe $currency$ mit $|currency|=m$ und $amount=n$ hat der Algorithmus moneyChange eine Laufzeit von O(m+n).

Beweis[Bearbeiten]

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[Bearbeiten]

Der Algorithmus moneyChange löst für $currency=\{1,2,5,10,20,50\}$ das Münzwechselproblem.

Beweis[Bearbeiten]

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

Die zweite Aussage zur Lösung war, dass $change[1]+...+change[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.