Problem wydawania reszty

Z Wikipedii

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: Usunięcie pierwszej osoby liczby mnogiej.. Dokładniejsze informacje o tym, co należy poprawić, być może znajdziesz na stronie dyskusji tego artykułu. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.

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ł?

Poniżej pokazujemy 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.

[edytuj] Algorytm zachłanny

Algorytm zachłanny jest poprawny dla tego problemu przy założeniu, że każda kwota, jaką trzeba wydać, oraz wszystkie dostępne nominały dzielą się bez reszty przez najmniejszy z dostępnych nominałów. Systemy monetarne w większości krajów (w tym w Polsce) są dostosowane tak, by ten warunek był zawsze spełniony, o ile są do dyspozycji wszystkie nominały będące w obrocie. Najmniejszym nominałem jest jeden grosz, a kwoty podaje się z dokładnością właśnie do jednego grosza. Jeśli w konkretnym zastosowaniu wszystkie kwoty wyrażają się w pełnych złotych albo z ułamkiem w dziesiątkach groszy, to odpowiednio najmniejszym niezbędnym nominałem będzie ich największy wspólny dzielnik – nominał 1 zł albo 10 gr.

Również podany powyżej przykład spełnia to założenie, bo zarówno wymagana kwota (13) i wszystkie dostępne nominały (1, 2, 5) są podzielne bez reszty przez najmniejszy z nominałów (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 – żądana kwota; wg przykładu 13; w każdym kroku pomniejszana o n

n – największy element zbioru nominałów mniejszy lub równy k

x – liczba potrzebnych monet; początkowo 0, w każdym kroku o 1 większa

Zaletą powyższego algorytmu jest szybkość i prostota implementacji. Algorytm zachłanny zapisany w C++ to zaledwie klika linijek:

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

Analogiczny algorytm w Pascalu (funkcja mogłaby zajmować mniej linijek, ale jest rozpisana z myślą o przejrzystości):

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.

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

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

Taki algorytm jest bardziej uniwersalny, ale nieco trudniejszy w implementacji. Zapisany w C++, wygląda tak:

#define INFINITY 2147483647 // nieskończoność definiujemy umownie jako górny kres typu integer
   /* 
     ...
   */
   // a – liczba nominałów, k – żądana kwota
   int T[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ł
     scanf("%d",&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.
   }