Das Änderungsproblem befasst sich mit der Frage, die Mindestanzahl von Münzen (bestimmter Stückelungen) zu finden, die sich zu einem bestimmten Geldbetrag addieren. Es ist ein Sonderfall des Integer-Rucksackproblems und hat Anwendungen, die breiter sind als nur Währung.

Es ist auch die häufigste Variante des Münzwechselproblems, ein allgemeiner Partitionsfall, bei dem angesichts der verfügbaren Stückelungen einer unendlichen Menge von Münzen das Ziel darin besteht, die Anzahl der möglichen Möglichkeiten zu ermitteln, eine Änderung für einen bestimmten Geldbetrag vorzunehmen, ohne die Reihenfolge der Münzen zu berücksichtigen.wir wählen die Lösung, bei der wir für einen bestimmten Betrag eine Mindestanzahl von Münzen angeben müssen.

1. Gierige Methode

2. Dynamische Methode

Dynamische Programmierung

Eine klassische dynamische Programmierstrategie arbeitet nach oben, indem sie die Kombinationen aller kleineren Werte ermittelt, die sich zum aktuellen Schwellenwert summieren würden.Aus diesem Grund kann dieser dynamische Programmieransatz eine Anzahl von Schritten erfordern, die in der Zielmenge W mindestens quadratisch sind.

optimaler Münzwechsel Wir haben gesehen, dass Sie Änderungen mit einem System von Stückelungen vornehmen möchten, wobei die geringstmögliche Anzahl von Münzen verwendet wird. Manchmal gibt der gierige Algorithmus die optimale Lösung. Aber manchmal nicht – ein Beispiel war das System (12, 5, 1), bei dem der dynamische Algorithmus 15 = ergibt 12 + 1 + 1 + 1 aber eine bessere Antwort ist 15 = 5 + 5 + 5. aber dynamisch gibt immer eine optimale Lösung oder mögliche minimale Münzen innerhalb dieses Nenners.

Schritte: –

Wir werden die minimale Nr. münzen für den Betrag erforderlich .
Betrag ist der Betrag, für den wir die Änderung vornehmen.

wir werden zuerst min. Nein. von Münzen erforderlich i.e., min = INFINITY
Dies bedeutet, dass wir zunächst nicht wissen, wie viele Münzen benötigt werden.

Dann überprüfen wir jede Stückelung Münzen und sehen, ob es verwendet werden kann, um die Lösung zu erhalten.

Wenn es möglich ist, aktualisieren wir die Variablen min und coin.
wo, min = Minimum nein. anzahl der Münzen, die für die Änderung des Betrags erforderlich sind
Münze = erster Index der Münze in der Lösung

Beispiel:

Betrag = 5

Münzen = {1,2,3}

Möglichkeiten, Änderungen vorzunehmen = 5