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: 14.
Dodano: 5 października 2016 11:19, ostatnia edycja: 30 stycznia 2019 13:59.
Zobacz też
Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.
Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).
Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.
Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.
Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.
Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.
W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.