początkowo 0
Algorytm zachłanny Algorytm zachłanny jest poprawny dla tego problemu w większości stosowanych obecnie systemów monetarnychXuan Cai, Yiyuan Zheng, „Canonical Coin Systems for Change-Making Problems”, ., jednak nie działa np. dla systemu (1, 4, 5) (kontrprzykładem jest kwota 8).
W tym przypadku, algorytm będzie wartość: k – w każdym kroku pomniejszał o n n – porównywał z wartością k, by stwierdzić, czy jest ona mniejsza lub równa x – w każdym kroku zwiększał o 1
Algorytm odejmuje od zadanej kwoty największy spośród nominałów mniejszych i równych kwocie. Następnie, o ile kwota jest większa od zera, powtarza czynność. Liczba powtórzeń jest liczbą potrzebnych monet.
Dla powyższego przykładu algorytm zadziała następująco:
k 13 8 3 1 n 5 5 2 1 x 1 2 3 4
Zaletą powyższego algorytmu jest szybkość i prostota implementacji.
Implementacja Algorytm zachłanny zapisany w C++:
// k – zadana kwota, x=0 – wynik // N – zbiór nominałów (tablica o długości l) while (k > 0) { // dopóki kwota większa od zera int n = 0; // n – maksymalny nominał mniejszy lub równy kwocie for (int i = 0; i < l; ++i) { // wśród wszystkich nominałów... if ((N[i] <= k) && (N[i] > n)) { // ...znajdź n n = N[i];
k -= n; // pomniejsz kwotę o n ++x;