Problem wydawania reszty (ang. change-making problem) – problem obliczeniowy polegający na tym, aby mając określony zbiór nominałów wyrazić daną kwotę za pomocą jak najmniejszej liczby monet. Jest to szczególny przypadek problemu plecakowego.

Formalny opis problemu

Dany jest ciąg nominałów A=(c₁, c₂, …, c_n) oraz kwota do wydania r. Nominały są posortowane rosnąco (c₁ < c₂ < … < c_n). Należy wyznaczyć takie nieujemne współczynniki k₁, k₂, …, k_n, że k₁c₁+k₂c_c+…+k_nc_n=r, a suma k₁+k₂+…+k_n jest jak najmniejsza.

Dla uproszczenia można przyjąć, że wszystkie nominały oraz kwota r muszą być podzielne przez najmniejszy nominał c₁ (np. najmniejszy nominał jest równy 1, a pozostałe nominały i kwota do wydania to liczby naturalne). Zapobiega to sytuacji, w której kwota r nie jest możliwa do wydania.

Problem może występować w dwóch wariantach, które w anglojęzycznej literaturze są określane jako bounded (dosłownie: ograniczony) i unbounded (dosłownie: nieograniczony). Problem ograniczony polega na tym, że dysponujemy jedynie określoną liczbą monet każdego nominału. W problemie nieograniczonym liczba monet każdego nominału jest dowolna. W artykułach dotyczących konkretnych algorytmów rozważamy problem w wersji nieograniczonej.

REKLAMA

Algorytmy rozwiązujące problem

• Algorytm zachłanny – algorytm ten jest szybki i intuicyjny, ale nie dla każdego zbioru nominałów daje gwarancję znalezienia rozwiązania optymalnego.
• Algorytm oparty na programowaniu dynamicznym – wolniejszy, ale zawsze zwracający rozwiązanie optymalne. Algorytm ten ma również inny wariant.
• Algorytm oparty na metodzie branch-and-bound – również zawsze zwracający rozwiązanie optymalne. Algorytm ten jest opisany w książce Knapstack Problems, Algorithms and Computer Implementations (link w bibliografii).

Bibliografia

• Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010, ISBN 9788373356689.
• S. Martello, P. Toth, Knapstack Problems: Algorithms and Computer Implementations, Nowy Jork, 1990, ISBN 0471924202.