Problem wydawania reszty

Kasjer wydający resztę sięga po największą monetę, która się mieści, potem po następną, i dla euro czy dolarów zawsze daje to najmniej monet. Wystarczy jednak zmienić monety na 1, 3 i 4, a ten sam nawyk zapłaci 6 trzema monetami, choć wystarczyłyby dwie. Programowanie dynamiczne znajduje prawdziwe minimum dla dowolnych monet.

Rząd kwot, każda z najmniejszą liczbą monet, które ją dają, nad monetami trzech różnych rozmiarów
Rząd kwot, każda z najmniejszą liczbą monet, które ją dają, nad monetami trzech różnych rozmiarów

Dwa pytania

Problem wydawania reszty występuje w dwóch wersjach. Pierwsza pyta o najmniejszą liczbę monet, które dają dokładną kwotę; to właśnie ją nazywa się zwykle problemem wydawania reszty. Druga pyta, ile różnych kombinacji monet daje tę kwotę. W obu każdego rodzaju monety można używać dowolnie wiele razy i obie rozwiązuje się, budując odpowiedź dla każdej kwoty z odpowiedzi dla mniejszych kwot.

Najmniej monet krok po kroku

Utwórz rząd komórek dla kwot od 0 do kwoty docelowej. Kwota 0 wymaga 0 monet; każda inna kwota zaczyna od nieskończoności. Przechodź po kwotach po kolei i dla każdej wypróbuj każdą monetę c, która się mieści: komórka dla kwoty minus c, plus jedna moneta, to kandydat. Zachowaj najmniejszego. Każda komórka zależy tylko od komórek po jej lewej stronie, które są już ostateczne, więc jedno przejście wypełnia cały rząd.

Przykład

Przy monetach 1, 3 i 4: kwota 1 wymaga 1 monety, 2 wymaga 2, 3 wymaga 1 (jednej trójki), a 4 wymaga 1. Dla 5 próbujemy 1 (4 wymaga 1, więc 2 monety), 3 (2 wymaga 2, więc 3 monety) i 4 (1 wymaga 1, więc 2 monety): najlepiej 2. Dla 6 próbujemy 1 (5 wymaga 2, więc 3), 3 (3 wymaga 1, więc 2) i 4 (2 wymaga 2, więc 3): najlepiej 2, przez 3 + 3. Algorytm zachłanny zapłaciłby 4 + 1 + 1.

Liczenie sposobów

Aby liczyć kombinacje, dodawaj monety po jednej. Mając tylko pierwszą monetę, każdą kwotę można uzyskać na jeden sposób albo wcale. Gdy dochodzi nowa moneta c, sposoby uzyskania kwoty a to dawne sposoby, bez c, plus sposoby uzyskania a − c, przy których c znów jest dozwolona, bo każdy z nich staje się sposobem uzyskania a po dodaniu jeszcze jednej monety c. Przy monetach 1, 2 i 5 są 4 sposoby uzyskania 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 oraz 1 + 1 + 1 + 1 + 1.

Kiedy algorytm zachłanny wystarcza

System monet, dla którego algorytm zachłanny zawsze daje najmniej monet, nazywa się kanonicznym. Większość współczesnych walut jest tak zaprojektowana, a w 1994 roku David Pearson opisał test, który sprawdza system monet w liczbie kroków rosnącej tylko wielomianowo względem liczby monet. Dawne monety brytyjskie nie były kanoniczne: algorytm zachłanny płaci 48 pensów półkoronówką, szylingiem i sześciopensówką, choć wystarczyłyby dwa floreny.

Wypróbuj sam

Otwórz aplikację, przejdź do widoku Tabela i naciśnij Krok. W trybie Najmniej monet pomarańczowa komórka to kwota, która jest właśnie obliczana, a niebieska komórka to mniejsza kwota, którą zostawia moneta; wiersz poniżej zapamiętuje ostatnią monetę, a na końcu monety odczytuje się wstecz wzdłuż niego. Przełącz na Liczba sposobów i obserwuj, jak liczby rosną wiersz po wierszu, w miarę jak dochodzą kolejne monety.

Często zadawane pytania

Czy problem wydawania reszty to problem plecakowy?

Bliski krewny. Wersja z najmniejszą liczbą monet to nieograniczony problem plecakowy, w którym każda moneta jest przedmiotem o wadze równej jej nominałowi, plecak trzeba wypełnić dokładnie, a celem jest jak najmniejsza liczba przedmiotów.

Jaka jest złożoność czasowa?

O(k·A) dla k rodzajów monet i kwoty A, w obu wersjach. Tabela dla najmniejszej liczby monet ma A + 1 komórek, a tabela dla liczby sposobów (k + 1)·(A + 1), choć wystarczy jeden wiersz, jeśli komórki aktualizuje się w miejscu.

Dlaczego liczyć monety w stałej kolejności?

Gdyby każda kwota próbowała każdej monety, 1 + 2 i 2 + 1 zostałyby policzone jako dwa sposoby. Dodawanie monet po jednym wierszu sprawia, że kombinacja zawsze jest budowana najpierw z wcześniejszych monet, więc każda jest liczona dokładnie raz.

Czy da się odczytać monety dla liczby sposobów?

Nie jako jedną odpowiedź, bo jest ich wiele. Wersja z najmniejszą liczbą monet zapamiętuje ostatnią monetę każdej kwoty, a to wystarcza, by odtworzyć jedną najlepszą kombinację.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj wydawanie reszty