Problem wydawania reszty
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=(c1, c2, …, cn) oraz kwota do wydania r. Nominały są posortowane rosnąco (c1 < c2 < … < cn). Należy wyznaczyć takie nieujemne współczynniki k1, k2, …, kn, że k1c1+k2cc+…+kncn=r, a suma k1+k2+…+kn jest jak najmniejsza.
Dla uproszczenia można przyjąć, że wszystkie nominały oraz kwota r muszą być podzielne przez najmniejszy nominał c1 (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.
Algorytmy rozwiązujące problem
Do rozwiązania problemu wydawania reszty można zastosować m.in. następujące algorytmy:- 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.
- S. Martello, P. Toth, Knapstack Problems, Algorithms and Computer Implementations, 1990. (link) [dostęp: 2 grudnia 2016]
Liczba głosów: 0.
Dodano: 5 października 2016 11:19, ostatnia edycja: 24 marca 2017 10:28.
Zobacz też
Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.
Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.
- Metoda zstępująca z zapamiętywaniem polega na rekurencyjnym wywoływaniu funkcji z zapamiętywaniem wyników. Metoda ta jest podobna do metody dziel i zwyciężaj – różni się od niej tym, że jeśli rozwiązanie danego problemu jest już w tabeli z wynikami, to należy je po prostu stamtąd odczytać.
- Metoda wstępująca polega na rozwiązywaniu wszystkich możliwych podproblemów, zaczynając od tych o najmniejszym rozmiarze. Wówczas w momencie rozwiązywania podproblemu na pewno są już dostępne rozwiązania jego podproblemów. W tym podejściu nie zużywa się pamięci na rekurencyjne wywołania funkcji. Może się jednak okazać, że część podproblemów została rozwiązana nadmiarowo (nie były one potrzebne do rozwiązania głównego problemu).
Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).
Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.
Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.