Problem wydawania reszty

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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

Rozwiązanie[edytuj | edytuj kod]

Poniżej pokazano dwa popularne rozwiązania tego problemu 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.

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[edytuj | edytuj kod]

Algorytm zachłanny jest poprawny dla tego problemu w większości stosowanych obecnie systemów monetarnych[1], 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[edytuj | edytuj kod]

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
}

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.
   }

Przypisy

  1. Xuan Cai, Yiyuan Zheng, "Canonical Coin Systems for Change-Making Problems", [1]