Rückgeld-Algorithmus

Owned by Former user (Deleted)
Last updated: März 09, 2021
2 min read


Erkärung:

Stellen Sie sich diesen Algorithmus wie eine(n) Kassierer(in) vor, der/die einen vorgegebenen Betrag an Rückgeld mit dem Bargeld aus der Kasse zurückzahlen muss. Um diesen Vorgang unkompliziert abzuwickeln wird er/sie vermutlich nicht so lange nach 1ct-Münzen greifen bis der Betrag irgendwann erfüllt ist. Denn mit 1ct-Münzen kann man zwar genau arbeiten, allerdings benötigt man sehr viele um schon relativ kleine Beträge zu kreieren. Die naheliegendste und auch aus dem Alltag bekannteste Strategie ist, ersteinmal soviel Geld wie möglich mit so wenig Handgriffen wie möglich zurück zu zahlen und dann den Restbetrag mit kleineren Geld-"Stücken" zurück zu zahlen. So wird bei dem Zurückzahlen von einem Betrag von beispielsweise 9.99€ zuerst nach Ausgabe von 9.90€ zu den 1-, 2- und 5-ct Münzen gegriffen.

Nach diesem Prinzip funktioniert der Rückgeld-Algorithmus in der Anwendung "Schornstruktor". Das Programm erstellt eine interne Liste mit den im Abschnitt verfügbaren Längenelemente. Daraufhin werden die verfügbaren Längenelemente der Größe nach sortiert und es wird nacheinander das nächstgrößte selektiert und errechnet wieviele Längenelemente der aktuellen Selektion in die leere Restlänge des Abschnitts passen. 


Beispiel:

Ein Abschnitt hat nach Einsetzen eines Bogens noch 11.86m die mit folgenden Rohrtypen gefüllt werden sollen:

  • Rohr A (2m)
  • Rohr B (1.90m)
  • Rohr C (0.5m)
  • Rohr D (0.2m)


  • Rohr A passt maximal 5 mal in die Soll-Länge des Abschnitts ohne diesen zu überschreiten also 5 * Rohr A (es verbleiben 11.86m - 5 * 2m = 1.86m)
  • Rohr B passt gar nicht mehr in die Restlänge des Abschnitts und wird deshalb gar nicht verwendet
  • Rohr C passt maximal 3 mal in die restliche Soll-Länge von 1.86m also 3 * Rohr C (es verbleiben 1.86m - 3 * 0.5m = 0.36m)
  • Rohr D ist das letzte Rohr also wird jetzt nicht mehr darauf geachtet den Abschnitt nicht zu überschreiten, sondern nur noch die Restlänge zu füllen also 2 * Rohr D (es verbleiben 0.36m - 2 * 0.2m = -0.04m)

In diesem Beispiel wird nocheinmal veranschaulicht, dass durch die Algorithmen kein perfektes Ergebnis erzielt wird. Es kann auch vorkommen, dass eine einfache Lösung für eine Soll-Länge auf der Hand liegt, die eine perfekte Lösung darstellt und trotzdem von der der Längenoptimierung nicht gefunden wird.