Kurs:Algorithmen und Datenstrukturen/Vorlesung/Greedyalgorithmen Wechselgeldalgorithmus

Aus Wikiversity
Zur Navigation springen Zur Suche springen




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.

Analyse[Bearbeiten]

Theorem[Bearbeiten]

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

Beweis[Bearbeiten]

  • 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

Theorem[Bearbeiten]

Für Eingabe mit und 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 das Münzwechselproblem.

Beweis[Bearbeiten]

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.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg