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; początkowo 0

Algorytm zachłanny Algorytm zachłanny jest poprawny dla tego problemu w większości stosowanych obecnie systemów monetarnychXuan Cai, Yiyuan Zheng, „Canonical Coin Systems for Change-Making Problems”, ., jednak nie działa np. dla systemu (1, 4, 5) (kontrprzykładem jest kwota 8).

W tym przypadku, algorytm będzie wartość: k – w każdym kroku pomniejszał o n n – porównywał z wartością k, by stwierdzić, czy jest ona mniejsza lub równa x – w każdym kroku zwiększał o 1

Algorytm odejmuje od zadanej kwoty największy spośród nominałów mniejszych i równych kwocie. Następnie, o ile kwota jest większa od zera, powtarza czynność. Liczba powtórzeń jest liczbą potrzebnych monet.

Dla powyższego przykładu algorytm zadziała następująco:

k 13 8 3 1 n 5 5 2 1 x 1 2 3 4

Zaletą powyższego algorytmu jest szybkość i prostota implementacji.

Implementacja Algorytm zachłanny zapisany w C++:

// k – zadana kwota, x=0 – wynik // N – zbiór nominałów (tablica o długości l) while (k > 0) { // dopóki kwota większa od zera int n = 0; // n – maksymalny nominał mniejszy lub równy kwocie for (int i = 0; i < l; ++i) { // wśród wszystkich nominałów... if ((N[i] <= k) && (N[i] > n)) { // ...znajdź n n = N[i];

k -= n; // pomniejsz kwotę o n ++x; // zwiększ wynik o 1 }

Wadą rozwiązania zachłannego jest brak możliwości wykorzystania w przypadku, gdy nominały mogą być tak dobrane, że nie zawsze znajdzie się nominał, przez który kwota dzieli się bez reszty. Przykładem jest sytuacja z życia codziennego: nominały w bankomatach to zwykle 20, 50, 100 i 200 zł. Algorytm zachłanny zastosowany przy takich nominałach dla kwoty 60 zł nie zadziałałby – w pierwszym kroku pomniejszyłby kwotę o 50 zł, pozostawiając 10 zł; tak mała kwota nie może być wydana przy użyciu ww. nominałów.

Algorytm z wykorzystaniem programowania dynamicznego Dzięki wykorzystaniu programowania dynamicznego możliwe jest znalezienie rozwiązania dla tego problemu przy dowolnym zbiorze nominałów i dowolnej kwocie. Algorytm polega na przetwarzaniu kolejnych nominałów i obliczeniu minimalnej liczby potrzebnych monet dla wydania kwot od 0 do k. Przy analizie kolejnego nominału wykorzystywane są informacje pozyskane w czasie wcześniejszych analiz. Jeśli nie będzie możliwe wydanie kwoty przy użyciu dostępnych nominałów, zostanie zwrócony wynik „nieskończoność”.

Przebieg algorytmu: Zapisz w postaci tablicy T liczbę monet potrzebną do wydania każdej kwoty od 0 do k. Pierwotnie (przed przeanalizowaniem jakiegokolwiek nominału) dla kwoty 0 liczba ta wynosi 0, a dla każdej kwoty większej od 0 – „nieskończoność”. Wczytaj nominał n. Dla każdej kwoty j od 0 do k-n wykonuj: sprawdź, czy wiadomo, iloma monetami dotychczas wczytanych nominałów można wydać kwotę j (tzn. czy element tablicy T[j] ma wartość „skończoną”); jeżeli tak, to sprawdź, czy dodając do nich jedną monetę nominału n, uzyskasz liczbę monet (T[j]+1) mniejszą, niż dotychczas wyznaczona dla kwoty j+n (T[j+n]); jeśli tak, to zapisz tę nową, mniejszą liczbę monet dla powiększonej kwoty (przypisz T[j]+1 do T[j+n]). Jeśli do wczytania pozostały jeszcze jakieś nominały, przejdź do kroku 2. Wynik dla kwoty k zapisany jest w T[k].

Dla podanego na początku artykułu przykładu zadziała następująco:

n T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 – 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 2 0 1 1 2 2 3 3 4 4 5 5 6 6 7 5 0 1 1 2 2 1 2 2 3 3 2 3 3 4

Przy odwrotnej kolejności wczytywania nominałów wyniki będą następujące:

n T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 – 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 5 0 ∞ ∞ ∞ ∞ 1 ∞ ∞ ∞ ∞ 2 ∞ ∞ ∞ 2 0 ∞ 1 ∞ 2 1 3 2 4 3 2 4 3 5 1 0 1 1 2 2 1 2 2 3 3 2 3 3 4

Implementacja Taki algorytm jest bardziej uniwersalny, ale nieco trudniejszy w implementacji.

Przykład kodu w C++:

#define INFINITY 2147483647 // nieskończoność definiujemy umownie jako górny kres typu integer /* ... */ // a – liczba nominałów, k – żądana kwota int* T = new int[k+1]; // utwórz tablicę T o zakresie od 0 do k T = 0; // dla kwoty 0 potrzebujesz 0 monet int i; for (i=1;i<=k;++i) { // dla każdej kwoty od 1 do k T[i]=INFINITY; // potrzebujesz nieskończoność monet } for (i=1;i<=a;++i) { // dla każdego nominału wykonuj: int n; // n – aktualnie analizowany nominał cin >> n; // wczytaj nominał for (int j=0;j<=k-n;++j) { // dla j=0 do k-n wykonuj: if (T[j] < INFINITY) { // jeżeli T[j] już ma przypisaną wartość i jeżeli if (T[j]+1 < T[j+n]) { // dodanie monety zmniejszy liczbę monet dla kwoty j+n, T[j+n] = T[j]+1; // to zapisz nową liczbę monet dla zwiększonej kwoty.

Przypisy

Linki zewnętrzne Problem wydawania reszty w Encyklopedii Algorytmów

Kategoria:Algorytmika