ROZWIĄZYWANIE PROBLEMÓW

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

Rozwiązanie

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; według przykładu 13

n – największy element zbioru nominałów

X – liczba potrzebnych monet; początkowo 0

SCHEMAT  BLOKOWY

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.

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