Einfache dynamische ProgrammierungBearbeiten
Eine klassische Strategie der dynamischen Programmierung arbeitet aufwärts, indem sie die Kombinationen aller kleineren Werte findet, die in der Summe den aktuellen Schwellenwert ergeben würden. Daher werden bei jedem Schwellenwert alle vorherigen Schwellenwerte potenziell berücksichtigt, um auf den Zielbetrag W hinzuarbeiten. Aus diesem Grund erfordert dieser Ansatz der dynamischen Programmierung eine Anzahl von Schritten, die O(nW) ist, wobei n die Anzahl der Münzarten ist.
ImplementationEdit
Das Folgende ist eine Implementierung der dynamischen Programmierung (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, mit den gegebenen Münzen Wechselgeld zu verdienen. Eine zweite Matrix kann verwendet werden, um die Menge der Münzen für die optimale Lösung zu erhalten.
def _get_change_making_matrix(set_of_coins, r: int): m = for _ in range(len(set_of_coins) + 1)] for i in range(1, r + 1): m = float('inf') # By default there is no way of making change return mdef 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. if coins == r: m = 1 # coins cannot be included. # Use the previous solution for making r, # excluding coins. elif coins > r: m = m # coins can be used. # Decide which one of the following solutions is the best: # 1. Using the previous solution for making r (without using coins). # 2. Using the previous solution for making r - coins (without # using coins) plus this 1 extra coin. else: m = min(m, 1 + m]) return m
Dynamische Programmierung mit dem probabilistischen FaltungsbaumBearbeiten
Der probabilistische Faltungsbaum kann auch als effizienterer dynamischer Programmieransatz verwendet werden. Der probabilistische Faltungsbaum fasst Münzpaare zusammen, um alle Beträge zu erzeugen, die von diesem Münzpaar erzeugt werden können (wenn keine Münze vorhanden ist, wenn nur die erste Münze vorhanden ist, wenn nur die zweite Münze vorhanden ist und wenn beide Münzen vorhanden sind), und fügt anschließend Paare dieser zusammengeführten Ergebnisse auf dieselbe Weise zusammen. Dieser Vorgang wird so lange wiederholt, bis die letzten beiden Sammlungen von Ergebnissen zu einer einzigen zusammengeführt sind, was zu einem ausgewogenen Binärbaum mit W log(W) solcher Zusammenführungsoperationen führt. Durch die Diskretisierung der Münzwerte kann jede dieser Zusammenführungsoperationen über eine 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 unterquadratischen Anzahl von Schritten zu erreichen: Jede Faltung kann in n log(n) durchgeführt werden, und die anfänglichen (zahlreicheren) Fusionsoperationen benötigen ein kleineres n, während die späteren (weniger zahlreichen) Operationen n in der Größenordnung von W erfordern.
Die probabilistische, auf Faltungsbäumen basierende Methode der dynamischen Programmierung löst auch effizient die probabilistische Verallgemeinerung des Wechselgeldproblems, bei der die Ungewissheit oder Unschärfe des Zielbetrags W ihn zu einer diskreten Verteilung statt zu einer festen Größe macht, bei der der Wert jeder Münze ebenfalls unscharf sein darf (z. B. wenn ein Wechselkurs in Betracht gezogen wird) und bei der verschiedene Münzen mit bestimmter Häufigkeit verwendet werden können.
Gierige MethodeBearbeiten
Für die so genannten kanonischen Münzsysteme, wie sie in den USA und vielen anderen Ländern verwendet werden, führt ein gieriger Algorithmus, bei dem der größte Münzwert gewählt wird, der nicht größer ist als der verbleibende Betrag, zu einem optimalen Ergebnis. Bei beliebigen Münzsystemen ist dies jedoch nicht der Fall. Wären die Münzwerte beispielsweise 1, 3 und 4, dann würde der gierige Algorithmus drei Münzen (4,1,1) wählen, um 6 zu machen, während die optimale Lösung zwei Münzen (3,3) sind. Es ist möglich, in polynomieller Zeit zu testen, ob ein Münzsystem kanonisch ist (d.h. ob der gierige Algorithmus sein Wechselgeldproblem immer optimal löst).