Algorytm Zachłanny (Problem Wydawania Reszty)

Pojęcie "algorytmu zachłannego" (z ang. greedy algorithm) brzmi bardzo mądrze, ale w rzeczywistości spotykasz się z nim na co dzień w sklepie. Zachłanność polega na podejmowaniu najlepszej decyzji w danej chwili (czyli tzw. "decyzji lokalnie optymalnej"), z nadzieją, że doprowadzi to do najlepszego rozwiązania całego problemu.

Kasjer wydający Ci resztę nie analizuje milionów kombinacji monet. Bierze z kasetki największy możliwy nominał, jaki mieści się w reszcie do wydania. I powtarza to tak długo, aż wyda całą kwotę. To czysta "zachłanność"!

Jak przygotować dane pod algorytm?

Aby algorytm zadziałał, potrzebujemy "kasetki z monetami", czyli tablicy nominałów. Najważniejsza zasada: nominały muszą być posortowane malejąco (od największego do najmniejszego).

Dodatkowo, operowanie na liczbach zmiennoprzecinkowych (ułamkach) potrafi przysporzyć w informatyce wielu problemów (tzw. błędy precyzji w standardzie IEEE 754). Dlatego kwotę i nominały (PLN) często wyraża się jako liczby całkowite, czyli w... groszach!

• 5 złotych = 500
• 10 groszy = 10

Zrozumienie kodu krok po kroku

Oto uniwersalna implementacja, w której posiadając kwotę do wydania (w groszach), program "zjada" największe nominały.

[!NOTE] Zauważ, jak sprytnie użyto tutaj dzielenia całkowitego (ile razy dany nominał zmieści się w reszcie) oraz operacji modulo (co zostaje z kwoty po odjęciu tych nominałów). Pętla przelatuje przez każdy dostępny nominał, od 500 (5 zł) aż do 1 (1 gr).

Python

def wydaj_reszte(reszta):
    # Tablica nominałów w groszach posortowana malejąco
    nominaly = [500, 200, 100, 50, 20, 10, 5, 2, 1]
    
    print(f"Wydawanie reszty: {reszta / 100} zł")
    
    for moneta in nominaly:
        # Sprawdzamy, ile razy dana moneta zmieści się w naszej reszcie
        # np. ile monet '200' mieści się w '450'? Zmieści się 2 razy (dzielenie całkowite).
        ile_monet = reszta // moneta 
        
        if ile_monet > 0:
            print(f"Wydano {ile_monet} monet(y) o nominale {moneta / 100} zł")
            
            # Zmniejszamy naszą resztę używając reszty z dzielenia (modulo)
            # np. 450 % 200 pozostawi 50 groszy do wydania w kolejnych pętlach
            reszta = reszta % moneta

# Testowanie:
wydaj_reszte(480) # Wydaj 4,80 zł

C++

#include <iostream>
using namespace std;

void wydaj_reszte(int reszta) {
    // Tablica nominałów w groszach posortowana malejąco
    int nominaly[] = {500, 200, 100, 50, 20, 10, 5, 2, 1};
    // Zmienna przechowująca rozmiar tablicy (tutaj wynosi 9 elementów)
    int ile_nominalow = 9; 
    
    cout << "Wydawanie reszty: " << reszta / 100.0 << " zl" << endl;
    
    for (int i = 0; i < ile_nominalow; i++) {
        int moneta = nominaly[i];
        
        // Sprawdzamy, ile razy dana moneta zmieści się w naszej reszcie
        int ile_monet = reszta / moneta;
        
        if (ile_monet > 0) {
            cout << "Wydano " << ile_monet << " monet(y) o nominale " << moneta / 100.0 << " zl" << endl;
            
            // Zmniejszamy naszą resztę używając reszty z dzielenia (modulo)
            reszta = reszta % moneta;
        }
    }
}

int main() {
    wydaj_reszte(480); // Wydaj 4,80 zł
    return 0;
}

Kiedy ten algorytm NIE zadziała?

Pomimo że działa idealnie dla polskiego bilonu, to potrafi być "oszukany", jeśli wymyślimy sobie dziwny system monetarny. Załóżmy, że mamy monety o nominałach: 1, 3 i 4, a chcemy wydać resztę z 6.

Algorytm zachłanny zadziała tak:

1. Weźmie na start największą monetę: 4
2. Zostanie 2, więc weźmie monety mniejsze: 1 oraz znowu 1.
3. Łącznie wyda nam 3 monety (4 + 1 + 1 = 6).

A przecież wystarczyło wydać nam dwie monety o nominale 3! (3 + 3 = 6). W takim przypadku "zachłanność" nie doprowadziła nas do najbardziej optymalnego wyniku i trzeba posłużyć się algorytmami programowania dynamicznego. Na maturze jednak nikt Cię tak nie oszuka 😉