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, ISBN 9788373356689.
- S. Martello, P. Toth, Knapstack Problems: Algorithms and Computer Implementations, Nowy Jork, 1990, ISBN 0471924202.
Liczba głosów: 1.
Dodano: 5 października 2016 11:19, ostatnia edycja: 30 stycznia 2019 13:59.
Zobacz też
Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.
Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.
Quicksort, sortowanie szybkie – algorytm sortowania działający w średnim przypadku w czasie liniowo-logarytmicznym. Algorytm jest oparty na metodzie dziel i zwyciężaj. Nie jest to algorytm stabilny ani wykazujący zachowanie naturalne, jednak ze względu na efektywność jest algorytmem bardzo popularnym.
Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.
Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.