Änderungsproblem - Change-making problem
Das Änderungsproblem befasst sich mit der Frage, die minimale Anzahl von Münzen (mit bestimmten Nennwerten) zu finden, die sich zu einem bestimmten Geldbetrag summieren. Es ist ein Sonderfall des ganzzahligen Rucksackproblems und hat Anwendungen, die weit über die Währung hinausgehen.
Es ist auch die häufigste Variante des Münzwechselproblems , ein allgemeiner Fall der Aufteilung , bei dem es angesichts der verfügbaren Stückelungen einer unendlichen Menge von Münzen das Ziel ist, die Anzahl der möglichen Arten des Wechselns für eine bestimmte Währung herauszufinden Geldbetrag, ohne die Reihenfolge der Münzen zu berücksichtigen.
Es ist schwach NP-hart , kann aber durch dynamische Programmierung in pseudopolynomialer Zeit optimal gelöst werden .
Mathematische Definition
Münzwerte können durch einen Satz von n unterschiedlichen positiven ganzzahligen Werten (ganze Zahlen) modelliert werden , die in aufsteigender Reihenfolge als w 1 bis w n angeordnet sind . Das Problem ist: Bei gegebenem Betrag W , ebenfalls eine positive ganze Zahl, eine Menge von nicht negativen (positiven oder null) ganzen Zahlen { x 1 , x 2 , ..., x n } zu finden, wobei jedes x j repräsentiert, wie oft die Münze mit dem Wert w j wird verwendet, wodurch die Gesamtzahl der Münzen f ( W ) minimiert wird
unterliegt
Nicht-Währungsbeispiele
Eine Anwendung des Änderungsproblems kann in der Berechnung der Art und Weise gefunden werden, wie man in einem Dartspiel einen Neun-Dart-Finish erzielen kann.
Eine andere Anwendung ist die Berechnung der möglichen atomaren (oder isotopen) Zusammensetzung eines gegebenen Masse/Ladungs-Peaks in der Massenspektrometrie.
Methoden zum Lösen
Einfache dynamische Programmierung
Eine klassische dynamische Programmierstrategie arbeitet nach oben, indem sie die Kombinationen aller kleineren Werte findet, die sich zum aktuellen Schwellenwert summieren würden. Somit wird bei jedem Schwellenwert potentiell davon ausgegangen, dass alle vorherigen Schwellenwerte bis zum Zielbetrag W aufwärts arbeiten . Aus diesem Grund erfordert dieser dynamische Programmieransatz eine Anzahl von Schritten, die O( nW) ist, wobei n die Anzahl der Münzarten ist.
Implementierung
Das Folgende ist eine dynamische Programmierimplementierung (mit Python 3), die eine Matrix verwendet, um die optimalen Lösungen für Teilprobleme zu verfolgen, und die minimale Anzahl von Münzen oder "Unendlich" zurückgibt, wenn es keine Möglichkeit gibt, Änderungen mit dem vorzunehmen Münzen gegeben. Eine zweite Matrix kann verwendet werden, um den Münzsatz für die optimale Lösung zu erhalten.
def _get_change_making_matrix(set_of_coins, r: int):
m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]
for i in range(1, r + 1):
m[0][i] = float('inf') # By default there is no way of making change
return m
def change_making(coins, n: int):
"""This function assumes that all coins are available infinitely.
n is the number to obtain with the fewest coins.
coins is a list or tuple with the available denominations.
"""
m = _get_change_making_matrix(coins, n)
for c in range(1, len(coins) + 1):
for r in range(1, n + 1):
# Just use the coin coins[c - 1].
if coins[c - 1] == r:
m[c][r] = 1
# coins[c - 1] cannot be included.
# Use the previous solution for making r,
# excluding coins[c - 1].
elif coins[c - 1] > r:
m[c][r] = m[c - 1][r]
# coins[c - 1] can be used.
# Decide which one of the following solutions is the best:
# 1. Using the previous solution for making r (without using coins[c - 1]).
# 2. Using the previous solution for making r - coins[c - 1] (without
# using coins[c - 1]) plus this 1 extra coin.
else:
m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])
return m[-1][-1]
Dynamische Programmierung mit dem probabilistischen Faltungsbaum
Der probabilistische Faltungsbaum kann auch als effizienterer dynamischer Programmieransatz verwendet werden. Der probabilistische Faltungsbaum verschmilzt Münzpaare, um alle Beträge zu erzeugen, die durch dieses Münzpaar erzeugt werden können (wobei keine Münze vorhanden ist, nur die erste Münze vorhanden ist, nur die zweite Münze vorhanden ist und beide Münzen vorhanden sind) und anschließend Paare zusammenführen dieser zusammengeführten Ergebnisse auf die gleiche Weise. Dieser Vorgang wird wiederholt, bis die letzten beiden Ergebnissammlungen zu einer zusammengeführt sind, was zu einem ausgeglichenen Binärbaum mit W log(W) solcher Zusammenführungsoperationen führt. Darüber hinaus kann durch Diskretisierung der Münzwerte jede dieser Zusammenführungsoperationen über Faltung durchgeführt werden, die mit der schnellen Fourier-Transformation (FFT) oft effizienter durchgeführt werden kann . Auf diese Weise kann der probabilistische Faltungsbaum verwendet werden, um eine Lösung in einer subquadratischen Anzahl von Schritten zu erreichen: jede Faltung kann in n log(n) durchgeführt werden , und die anfänglichen (zahlreicheren) Zusammenführungsoperationen verwenden ein kleineres n , während die späteren (weniger zahlreichen) Operationen erfordern n in der Größenordnung von W .
Das probabilistische Faltungsbaum-basierte dynamische Programmierverfahren löst auch effizient die probabilistische Verallgemeinerung des Änderungsproblems, bei dem die Unsicherheit oder Unschärfe des Zielbetrags W ihn zu einer diskreten Verteilung anstelle einer festen Größe macht, wobei der Wert jeder Münze ebenfalls Fuzzy sein dürfen (z. B. wenn ein Wechselkurs berücksichtigt wird) und wo unterschiedliche Münzen mit bestimmten Häufigkeiten verwendet werden können.
Gierige Methode
Für die sogenannten kanonischen Münzsysteme, wie sie in den USA und vielen anderen Ländern verwendet werden, wird ein gieriger Algorithmus der Auswahl des größten Münzwerts, der nicht größer als der verbleibende zu machende Betrag ist, das optimale Ergebnis erzielen. Dies ist jedoch bei beliebigen Münzsystemen nicht der Fall. Wenn die Münzwerte zum Beispiel 1, 3 und 4 wären, dann würde der Gier-Algorithmus drei Münzen (4, 1, 1) wählen, um 6 zu erhalten, während die optimale Lösung zwei Münzen (3,3) ist. In polynomieller Zeit kann geprüft werden, ob ein Münzsystem kanonisch ist (d. h. ob der Greedy-Algorithmus sein Änderungsproblem immer optimal löst) .
Verwandte Probleme
Das " Problem der optimalen Denomination " ist ein Problem für Leute, die völlig neue Währungen entwerfen. Sie fragt, welche Stückelungen für die Münzen gewählt werden sollten, um die durchschnittlichen Wechselgeldkosten zu minimieren, d. h. die durchschnittliche Anzahl von Münzen, die zum Wechseln erforderlich sind. Die Version dieses Problems ging davon aus, dass die Personen, die das Wechselgeld vornehmen, die minimale Anzahl von Münzen (von den verfügbaren Nennwerten) verwenden. Eine Variante dieses Problems geht davon aus, dass die Leute, die Wechselgeld vornehmen, den "Greedy-Algorithmus" verwenden, um Wechselgeld vorzunehmen, selbst wenn dies mehr als die minimale Anzahl von Münzen erfordert. Die meisten aktuellen Währungen verwenden eine 1-2-5-Serie , aber einige andere Stückelungen würden weniger Münzstückelungen oder eine geringere durchschnittliche Anzahl von Münzen erfordern, um Wechselgeld zu tätigen oder beides.
