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.

Przykładowe zadanie

Dane są trzy nominały – 1 zł, 2 zł i 5 zł. Ile minimalnie monet potrzeba, by wydać 13 zł?

Rozwiązanie

Poniżej pokazano dwa popularne rozwiązania tego problemu dla wariantu problemu, w którym zakłada się dostępność dowolnej ilości monet każdego nominału: jedno przy pomocy algorytmu zachłannego, drugie z wykorzystaniem programowania dynamicznego.

Niech:

k – żądana kwota; wg 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 – zbior (tablica o długości l) nominalow
    while (k>0)                              // dopoki kwota wieksza od zera
    {
      int n=0;                                 // n – maksymalny nominal mniejszy lub rowny kwocie
      for (int i=0;i<l;++i)                    // wsrod wszystkich nominalow...
         if((N[i]<=k)&&(N[i]>n)) n=N[i];         // ...znajdz n
      k -= n;                                  // pomniejsz kwote o n
      ++x;                                     // zwieksz wynik o 1
    }

Przykład w C:

int greedy ( int * tab, int l, int k ) // tab - tablica z nominałami, l - długość tablicy, k - kwota do wydania
{
        int r = 0; // ilość monet do wydania
 
        while ( k > 0 )
        {
                l--;
                r += k / tab[l];
                k %= tab[l];
        }
 
        return r;
}

Analogiczny algorytm w Pascalu:

type
Tnominaly: array [1..n] of Integer;
 
{funkcja ilosc_monet zwraca najmniejszą liczbę monet potrzebnych, aby wydać zmienną
kwota typu Integer (uproszczenie dla skrócenia algorytmu) za pomocą nominałów 
których wartości są zawarte w tablicy nominaly typu Tnominaly (typ zadeklarowany powyżej).
n jest stałą oznaczającą długość tablicy.}
 
function ilosc_monet(kwota: Integer; nominaly: Tnominaly )
var
i, x: integer; {deklaracja zmiennych - i to iterator, a x - odpowiednik n z}
                     {powyższego przykładu}
begin
 
ilosc_monet:=0;
repeat
 
  i:=n;
 
  repeat
    x:=nominaly[i];
    if x>kwota then           {znajdowanie x}
      i:=i-1;
  until kwota>=x;
 
  ilosc_monet:=ilosc_monet+1;
  kwota:=kwota-x;
 
until kwota=0;
 
end;

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.

W bankomatach stosowany jest więc algorytm z wykorzystaniem programowania dynamicznego.

Algorytm z wykorzystaniem programowania dynamicznego

Dzięki wykorzystaniu programowania dynamicznego jest możliwe znalezienie bezbłędnego 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.
   }