problem z dokonywaniem zmian rozwiązuje kwestię znalezienia minimalnej liczby monet (niektórych nominałów), które sumują się do danej kwoty pieniędzy. Jest to szczególny przypadek integer knapsack problem, i ma zastosowania szersze niż tylko waluty.

jest to również najczęstsza odmiana problemu zmiany monety, ogólny przypadek podziału, w którym, biorąc pod uwagę dostępne nominały nieskończonego zestawu monet, celem jest znalezienie liczby możliwych sposobów dokonania zmiany dla określonej kwoty pieniędzy, bez uwzględniania kolejności monet.

dokonywanie zmian jest problemem minimalizacji, wybieramy rozwiązanie, w którym musimy podać minimalną ilość monet za daną kwotę.

2. Metoda dynamiczna

programowanie dynamiczne

klasyczna strategia programowania dynamicznego działa w górę, znajdując kombinacje wszystkich mniejszych wartości, które sumowałyby się do bieżącego progu.Tak więc, przy każdym progu, wszystkie poprzednie progi są potencjalnie uważane za działające w górę do kwoty docelowej W. Z tego powodu to dynamiczne podejście do programowania może wymagać kilku kroków, które są co najmniej kwadratowe w kwocie docelowej W.

optymalna zmiana monety widzieliśmy to, chcesz dokonać zmiany za pomocą systemu nominałów, przy użyciu jak najmniejszej liczby monet. Czasami algorytm chciwy daje optymalne rozwiązanie. Ale czasami tak nie jest-przykładem był system (12, 5, 1), Gdzie algorytm dynamiczny daje 15 = 12 + 1 + 1 + 1 ale lepsza odpowiedź to 15 = 5 + 5 + 5. ale dynamika zawsze daje optymalne rozwiązanie lub możliwą minimalną liczbę monet w tym mianowniku.

kroki: –

monet wymaganych na daną kwotę .
kwota to kwota, za którą dokonujemy zmiany.

najpierw ustawimy min. nie. wymaganych monet tj., min = nieskończoność
oznacza to, że początkowo nie wiemy, ile monet będzie potrzebnych.

następnie sprawdzamy każdy nominał i sprawdzamy, czy można go użyć, aby uzyskać rozwiązanie.

Jeśli jest to możliwe, aktualizujemy zmienne min i coin.
Gdzie, min = minimum nr monet wymaganych do dokonania zmiany kwoty
coin = pierwszy indeks monety w rozwiązaniu

przykład:

kwota = 5

monety = {1,2,3}

sposoby dokonania zmiany = 5