Problem wydawania reszty – zagadnienie z dziedziny algorytmiki, problem polegający na wybraniu z danego zbioru monet o określonych nominałach takiej konfiguracji, by wydać żądaną kwotę przy użyciu minimalnej liczby monet. Jego rozwiązania są wykorzystywane w automatach z napojami, bankomatach itd.
Definicja Niech będzie dany zbiór nominałów i kwota do wydania Można przyjąć, że nominały są posortowane rosnąco Należy wyznaczyć takie współczynniki (nieujemne, całkowite), żeby:
a wartość:
była jak najmniejsza.
Algorytmy
Poniżej pokazano dwa popularne rozwiązania dla wariantu problemu, w którym zakłada się dostępność dowolnej liczby monet każdego nominału: jedno przy pomocy algorytmu zachłannego, drugie z wykorzystaniem programowania dynamicznego. Przykładowo, dane są trzy nominały – 1 zł, 2 zł i 5 zł. Ile minimalnie monet potrzeba, by wydać 13 zł? Niech: k – żądana kwota; według przykładu 13 n – największy element zbioru nominałów x – liczba potrzebnych monet;