Je betaalt 8 yen met munten van 1 yen, 4 yen en 6 yen. Welke uitspraak over het aantal munten dat een gretig algoritme kiest (dat eerst zoveel mogelijk van de grootste munt gebruikt), vergeleken met het minimale aantal munten, is juist?

Antwoord: B. Het gretige algoritme gebruikt 3 munten en mist het minimum van 2

Het gretige algoritme neemt eerst één munt van 6 yen en betaalt de resterende 2 yen met twee munten van 1 yen: 3 munten. Maar twee munten van 4 yen betalen het bedrag met slechts 2. Omdat een gretig algoritme alleen telkens de keuze opstapelt die op dat moment het beste lijkt, is het voor sommige muntstelsels niet optimaal. Dynamisch programmeren, dat een tabel vult met het minimale aantal munten voor elk bedrag van 0 tot 8 yen, van klein naar groot, vindt altijd het minimum. Voor muntstelsels zoals de Japanse munten van 1, 5, 10, 50, 100 en 500 yen geeft het gretige algoritme altijd het minimum.