Kurs:Algorithmen und Datenstrukturen/Vorlesung/Greedyalgorithmen Wechselgeldalgorithmus




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:  

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  
2. dass eine Menge von Münzwerten zur Verfügung steht  

Die Ausgabe besteht dann aus ganzen Zahlen  . Dabei ist   die Anzahl der Münzen des Münzwertes für   für   und haben die Eigenschaften

1.  
2.   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.

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

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

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

  • 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

Der Algorithmus moneyChange löst für   das Münzwechselproblem.

Bei der Lösung musste zum Einen gelten, dass   ist. Da der Wert   stets um den Wert einer Münze   verringert wird, während   um eins inkrementiert wird, ist dies erfüllt.

Die zweite Aussage zur Lösung war, dass   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.