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: 15.
Dodano: 5 października 2016 11:19, ostatnia edycja: 30 stycznia 2019 13:59.
Zobacz też
Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.
W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:
Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:
Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.
Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.
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.
Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.
Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.