Zachłanny algorytm wydawania reszty – zawsze wybiera największy dostępny nominał.
Problem wydawania reszty polega na znalezieniu minimalnej liczby monet potrzebnych do wydania określonej kwoty przy użyciu dostępnych nominałów.
Algorytm zachłanny w każdym kroku wybiera największy nominał, który nie przekracza pozostałej kwoty do wydania. Jest szybki i prosty, ale nie zawsze daje optymalne rozwiązanie.
Działa optymalnie dla standardowych systemów monetarnych, takich jak polski (1, 2, 5, 10, 20, 50, 100, 200, 500) – to nie jest przypadek, system został tak zaprojektowany.
Kontrprzykład: dla nominałów [3, 4] i kwoty 6 algorytm zachłanny wybiera najpierw 4, potem nie może wydać reszty 2. Tymczasem optymalne rozwiązanie to 3 + 3. W takich przypadkach trzeba użyć algorytmu dynamicznego.
Na maturze: zadania zazwyczaj używają polskich nominałów, więc algorytm zachłanny wystarcza.
funkcja wydaj_zachlannie(nominaly, kwota): // sortujemy nominały malejąco posortuj nominaly malejąco monety ← pusta lista dla każdej monety w nominaly: dopóki kwota ≥ moneta: dodaj moneta do monety kwota ← kwota - moneta jeżeli kwota > 0: // nie da się wydać reszty zwróć "brak rozwiązania" zwróć monety
def wydaj_zachlannie(nominaly, kwota):
nominaly = sorted(nominaly, reverse=True)
monety = []
for moneta in nominaly:
while kwota >= moneta:
monety.append(moneta)
kwota -= moneta
if kwota > 0:
return None
return monety
# Przykład użycia
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 algorytm zawiedzie
print(wydaj_zachlannie([3, 4], 6))
# Wynik: NoneO(n + k)O(k)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: