Zachłanne wydawanie reszty – zawsze bierzemy największy pasujący nominał. Szybkie, ale nie zawsze optymalne.
Wydawanie reszty to zadanie: mamy kwotę do wydania i zestaw nominałów (monet), a chcemy wydać tę kwotę jak najmniejszą liczbą monet.
Jak działa algorytm zachłanny? „Zachłanny" znaczy, że na każdym kroku bierze to, co w danej chwili wygląda najlepiej, i nigdy tego nie cofa. Tutaj: zawsze wybieramy największy nominał, który jeszcze mieści się w pozostałej kwocie, odejmujemy go i powtarzamy, aż zostanie 0. Na przykład dla 437 bierzemy 200, znowu 200, potem 20, 10, 5, 2 – razem 6 monet.
Dlaczego czasem zawodzi? Bo bierze pod uwagę tylko „tu i teraz", a nie całość. Kontrprzykład: dla nominałów [3, 4] i kwoty 6 zachłanny bierze najpierw 4, a potem nie umie wydać reszty 2 – choć poprawne rozwiązanie to 3 + 3. Gdy zależy nam na wyniku dla dowolnych nominałów, trzeba użyć wersji dynamicznej.
Kiedy jest bezpieczny? Dla „normalnych" systemów monet, takich jak polski (1, 2, 5, 10, 20, 50, 100, 200, 500), algorytm zachłanny zawsze daje najmniejszą liczbę monet. To nie przypadek – takie zestawy są tak zaprojektowane, żeby zachłanne branie się opłacało.
Na maturze: zadania zwykle korzystają z polskich nominałów, więc zachłanny w zupełności wystarcza – warto tylko wiedzieć, że dla dziwnych nominałów może się mylić.
Prześledź krok po kroku algorytm zachłanny na polskich nominałach 500, 200, 100, 50, 20, 10, 5, 2, 1. W każdym kroku bierzemy największy nominał, który się jeszcze mieści w kwocie, i odejmujemy go. Powtarzamy, aż zostanie 0 – wtedy zebrane monety to rozwiązanie.
Naciśnij „Krok", aby wziąć pierwszą monetę, albo „Auto".
funkcja wydaj_zachlannie(nominaly, kwota): posortuj nominaly malejąco monety ← pusta lista dla nominał w nominaly: // od największego ile ← kwota div nominał // ile sztuk się mieści dopóki ile > 0: dodaj nominał do monety ile ← ile - 1 kwota ← kwota mod nominał // reszta po tym nominale jeżeli kwota > 0: zwróć "brak rozwiązania" // nie da się wydać tymi nominałami zwróć monety
def wydaj_zachlannie(nominaly, kwota):
"""Zachłannie wydaje resztę: zawsze bierze największy pasujący nominał."""
nominaly = sorted(nominaly, reverse=True)
monety = []
for nominal in nominaly:
ile = kwota // nominal # ile sztuk tego nominału się mieści
monety += [nominal] * ile # dorzuć je wszystkie naraz
kwota %= nominal # zostaje reszta po tym nominale
if kwota > 0:
return None # nie da się wydać tymi nominałami
return monety
nominaly_pl = [1, 2, 5, 10, 20, 50, 100, 200, 500]
print(wydaj_zachlannie(nominaly_pl, 437))
# Wynik: [200, 200, 20, 10, 5, 2]
# Kontrprzykład – tu zachłanny zawodzi (poprawnie: 3 + 3)
print(wydaj_zachlannie([3, 4], 6))
# Wynik: None#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> wydaj_zachlannie(vector<int> nominaly, int kwota) {
sort(nominaly.rbegin(), nominaly.rend()); // malejąco
vector<int> monety;
for (int nominal : nominaly) {
while (kwota >= nominal) {
monety.push_back(nominal);
kwota -= nominal;
}
}
return monety; // jeśli kwota > 0, reszty nie da się wydać tymi nominałami
}
int main() {
for (int m : wydaj_zachlannie({1,2,5,10,20,50,100,200,500}, 437)) cout << m << " ";
// Wynik: 200 200 20 10 5 2
}To taki, który na każdym kroku bierze najlepszy wybór „na teraz" i nigdy go nie cofa. Tutaj zawsze sięga po największy nominał, który się mieści – bez zastanawiania się nad całością.
Bo patrzy tylko na bieżący krok. Dla nominałów [3, 4] i kwoty 6 weźmie 4 i utknie na reszcie 2, choć poprawne rozwiązanie to 3 + 3. Dla nietypowych nominałów trzeba liczyć dynamicznie.
Dla typowych systemów monet, w tym polskiego. Są zaprojektowane tak, że branie największego nominału zawsze prowadzi do najmniejszej liczby monet.
Założenie, że zachłanny działa dla każdego zestawu nominałów. Zawsze sprawdź, czy nominały są „zwykłe" – inaczej wynik może nie być najlepszy albo w ogóle się nie uda.
Wydajemy resztę polskimi nominałami zachłannie. Kliknij Sprawdź.
Wydając 70, pierwszy bierzemy nominał . Wydając 437, po 200, 200, 20, 10, 5 zostaje jeszcze nominał .
Uzupełnij, iloma monetami wyda się każdą kwotę (nominały PL):
| Kwota | Liczba monet |
|---|---|
| 6 | |
| 30 | |
| 88 |
Zachłanny w każdym kroku wybiera nominał , który mieści się w pozostałej kwocie.
O(k)O(1)Jeśli dla każdego nominału bierzemy od razu kwota div nominał monet, to cały zestaw przechodzimy tylko raz – czas O(k), gdzie k to liczba nominałów (plus jednorazowe posortowanie ich malejąco). Poza samą listą wyniku pamięć jest stała, czyli O(1).
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: