Algorytm zachłanny charakteryzuje się tym, że w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepszego w danym momencie wyboru, wyboru rozwiązania podproblemu.
Algorytm omówię na przykładzie wydawania reszty przez automaty oraz wypłat gotówki z bankomatów.
Wydawanie reszty
Problem:
Jak dostępnymi monetami wydać resztę w taki sposób, by użyć ich jak najmniej.
Jakie będzie rozwiązanie dla reszty 6, a jakie dla 13?
RESZTA 6 | RESZTA 13 |
---|---|
![]() ![]() ![]() ![]() ![]() ![]() 6 monet ![]() ![]() ![]() ![]() ![]() 5 monet ![]() ![]() ![]() 3 monety ![]() ![]() 2 monety |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 13 monet ![]() ![]() ![]() ![]() ![]() ![]() ![]() 7 monet ![]() ![]() ![]() ![]() ![]() 5 monet ![]() ![]() ![]() ![]() 4 monety |
Widać zatem, że powinniśmy rozpocząć wydawanie reszty od najwyższych nominałów.
Algorytm przedstawia się następująco:
Realizacja:
Stosując dzielenie całkowite oraz resztę z dzielenia możemy funkcję zapisać krócej:
Zakładamy, że mamy większą ilość nominałów do wydawania.
Definiowanie działania dla każdej oddzielnie jest nieoptymalne.
W tym przypadku zastosujemy tablicę zawierającą nominały, którymi dysponujemy.
Deklaracja tablicy:
int nominaly[n] = {n1, n2, ... nn};
Procedura przyjmuje postać: