PRZYKŁADOWE ROZWIĄZANIE:

Zestawy monet niedające optymalnego rozwiązania: 

Aby znaleźć zestawy monet, dla których podejście zachłanne nie daje optymalnego rozwiązania dla wydawania reszty 18 złotych, musimy tak dobrać nominały monet, aby zachłanne wybieranie największych dostępnych nominałów nie prowadziło do minimalnej liczby monet. Jeden ze sposobów na osiągnięcie tego celu to takie dobranie nominałów, aby nie dało się wydać reszty 18 zł w sposób, który miałby minimalną liczbę monet.

Zestawy monet, dla których podejście zachłanne nie daje optymalnego rozwiązania (zakładając, że dysponujemy nieograniczoną liczbą monet o tych nominałach):

Nominały: [10, 5, 1]

1. Rozwiązanie podejścia zachłannego:

• Wydamy 1 monetę 10 zł.
• Pozostaje do wydania 8 zł.
• Wydamy 1 monetę 5 zł.
• Pozostaje do wydania 3 zł.
• Wydamy 3 monety 1 zł.

Ostatecznie, używając podejścia zachłannego, potrzebujemy 5 monet (10 zł + 5 zł + 1 zł + 1 zł + 1 zł + 1 zł) do wydania 18 złotych, co nie jest optymalnym wynikiem.

2. Rozwiązanie podejścia dynamicznego:

• Wykorzystamy tablicę T, w której będziemy przechowywać minimalną liczbę monet potrzebnych do wydania kwoty od 0 do 18 złotych.
• T[0] = 0, ponieważ nie potrzebujemy żadnych monet do wydania 0 złotych.
• T[1] = 1, bo potrzebujemy 1 monety 1 zł do wydania 1 zł.
• T[2] = 2, bo potrzebujemy 2 monet 1 zł do wydania 2 zł.
• T[3] = 3, bo potrzebujemy 3 monet 1 zł do wydania 3 zł.
• T[4] = 4, bo potrzebujemy 4 monet 1 zł do wydania 4 zł.
• T[5] = 1, bo potrzebujemy 1 monety 5 zł do wydania 5 zł.
• T[6] = 2, bo potrzebujemy 1 monety 5 zł i 1 monety 1 zł do wydania 6 zł.
• T[7] = 3, bo potrzebujemy 1 monety 5 zł i 2 monet 1 zł do wydania 7 zł.
• T[8] = 4, bo potrzebujemy 1 monety 5 zł i 3 monet 1 zł do wydania 8 zł.
• T[9] = 5, bo potrzebujemy 1 monety 5 zł i 4 monet 1 zł do wydania 9 zł.
• T[10] = 1, bo potrzebujemy 1 monety 10 zł do wydania 10 zł.
• T[11] = 2, bo potrzebujemy 1 monety 10 zł i 1 monety 1 zł do wydania 11 zł.
• T[12] = 3, bo potrzebujemy 1 monety 10 zł i 2 monet 1 zł do wydania 12 zł.
• T[13] = 4, bo potrzebujemy 1 monety 10 zł i 3 monet 1 zł do wydania 13 zł.
• T[14] = 5, bo potrzebujemy 1 monety 10 zł i 4 monet 1 zł do wydania 14 zł.
• T[15] = 2, bo potrzebujemy 1 monety 10 zł i 1 monety 5 zł do wydania 15 zł.
• T[16] = 3, bo potrzebujemy 1 monety 10 zł, 1 monety 5 zł i 1 monety 1 zł do wydania 16 zł.
• T[17] = 4, bo potrzebujemy 1 monety 10 zł, 1 monety 5 zł i 2 monet 1 zł do wydania 17 zł.
• T[18] = 5, bo potrzebujemy 1 monety 10 zł, 1 monety 5 zł i 3 monet 1 zł do wydania 18 zł.

Ostatecznie, aby wydać 18 złotych przy użyciu podejścia dynamicznego, potrzebujemy 5 monet (10 zł + 5 zł + 1 zł + 1 zł + 1 zł) - taki sam wynik jak przy podejściu zachłannym.

W tym konkretnym przypadku, zarówno podejście zachłanne, jak i podejście dynamiczne prowadzi do tego samego wyniku. Jednakże można dobrać takie zestawy nominałów, aby wynik podejścia zachłannego i dynamicznego różnił się.