Problem wydawania reszty

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 $w_{1},w_{2},\dots ,w_{n}$ i kwota do wydania $C.$ Można przyjąć, że nominały są posortowane rosnąco $(w_{1}<w_{2}<\ldots <w_{n}).$ Należy wyznaczyć takie współczynniki $x_{1},x_{2},\dots ,x_{n}$ (nieujemne, całkowite), żeby:

$\sum _{j=1}^{n}w_{j}x_{j}=C,$

a wartość:

$Z=\sum _{j=1}^{n}x_{j}$

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 monetarnych, 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 w/w 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] = 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.
            }
        }
    }
}

Linki zewnętrzne

• Problem wydawania reszty w Encyklopedii Algorytmów