Wydawanie reszty

Cel i geneza problemu

Algorytmy zachłanne (ang. greedy algorithms) to fundament teorii optymalizacji. Ich zadaniem jest znalezienie najlepszego rozwiązania spośród ogromnego zbioru możliwości.

Wyobraź sobie, że pracujesz w kasie w sklepie. Klient kupuje towar, płaci banknotem, a Ty musisz wydać mu określoną kwotę reszty. Twoim celem jest wydanie tej kwoty przy użyciu jak najmniejszej liczby monet i banknotów.

Dlaczego to ważne?

• Kasjer nie traci czasu na odliczanie drobniaków.
• W kasie wolniej kończą się monety (szczególnie te o niskich nominałach).
• Portfel klienta nie staje się nieznośnie ciężki.

Powrót do menu

Strategia i mechanizm działania

Algorytm nazywa się "zachłannym", ponieważ w każdym kroku podejmuje decyzję, która wydaje się w danym momencie lokalnie optymalna (bierze jak najwięcej), bez patrzenia w przyszłość.

Zasada działania krok po kroku:

1. Uporządkuj dostępne nominały od największego do najmniejszego (np. 500, 200, 100, 50, 20, 10, 5, 2, 1).
2. Sprawdź największy nominał. Jeśli jest mniejszy lub równy kwocie, którą musisz wydać, użyj go.
3. Oblicz liczbę monet metodą dzielenia całkowitego lub odejmij wartość nominału od kwoty reszty.
4. Zaktualizuj pozostałą kwotę za pomocą modulo (%).
5. Powtarzaj kroki, zmieniając nominał na mniejszy, aż reszta wyniesie 0.

Przykład: Reszta 68 zł. Najpierw bierzemy 50 zł (zostaje 18), potem 10 zł (zostaje 8), 5 zł (zostaje 3), 2 zł (zostaje 1), 1 zł i zostaje 0.

Powrót do menu

Implementacja w języku C++

Zakładamy, że R ∈ ℕ₀.

// Problem wydawania reszty - www.algorytm.org
#include <iostream>

using namespace std;

int main()
{
  // tablica dostepnych nominalow
  int N[9] = {500, 200, 100, 50, 20, 10, 5, 2, 1};
  int R, P, i;
  int licznik = 0; // Licznik lacznej liczby monet/banknotow

  cout << "Podaj reszte do wyplacenia: ";
  cin >> R;

  i = 0;
  while (R > 0 && i<9)
  {
    if (R >= N[i])
    {
      P = R / N[i];         // ile razy wydac dany nominal
      R = R % N[i];         // nowa reszta za pomoca modulo
      licznik += P;  // zwiekszenie licznika o liczbe monet
      cout << N[i] << " x " << P << endl;
    }
    i++;
  }

  cout << "Minimalna liczba banknotow/monet: " << licznik << endl;
  
  return 0;
}

Powrót do menu

Złożoność i ograniczenia

Algorytm zachłanny działa idealnie dla polskiego systemu monetarnego (tzw. systemu kanonicznego). Ale nie zawsze gwarantuje optymalne rozwiązanie!

Kontrprzykład:
Dla fikcyjnego systemu o nominałach: {1, 3, 4} i reszty 6:

• Zachłannie: Bierze 4, potem 1, potem 1 (łącznie 3 monety).
• Optymalnie: Bierze 3 i 3 (łącznie 2 monety).

Złożoność obliczeniowa:

• Czasowa: O(n) – gdzie n to liczba dostępnych nominałów. Czas wykonania nie zależy od wysokości kwoty.
• Pamięciowa: O(1) – stałe zapotrzebowanie na pamięć operacyjną.

Wniosek: Dla systemów niekanonicznych należy stosować programowanie dynamiczne.

Powrót do menu