Witam, czy mógłby ktoś wytłumaczyć mi działanie tego algorytmu (dla 7 i 10), bo kompletnie go nie rozumiem, a lista kroków mi nie pomaga...
0
1
Pytanie jest o algorytm dynamiczny, a nie zachłanny.
A teraz trochę chłopskiego rozumu: jak niby można osiągnąć 3zł za pomocą jednej monety? Albo jak osiągnąć 10zł za pomocą 2 monet?
Tabela dla 7:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 1 2 2 3 3 1 2 2 3 3 4 4 2
Skoro 0zł można osiągnąć za pomocą 0 monet, to 7zł można osiągnąć za pomocą 1 monety, i jest to mniejsza liczba niż 4, więc zmieniamy wartość pod 7 z 4 na 1.
Skoro 1zł można osiągnąć za pomocą 1 monety, to 8zł można osiągnąć za pomocą 2 monet, i jest to mniejsza liczba niż 4, więc zmieniamy
Skoro 3zł można osiągnąć za pomocą 2 monet, to 10zł można osiągnąć za pomocą 3 monet, i jest to mniejsza liczba niż 5, więc zmieniamy
Skoro 5zł można osiągnąć za pomocą 3 monet, to 12zł można osiągnąć za pomocą 4 monet, i jest to mniejsza liczba niż 6, więc zmieniamy
Skoro 7zł można osiągnąć za pomocą 1 monety, to 14zł można osiągnąć za pomocą 2 monet, i jest to mniejsza liczba niż 7, więc zmieniamy
Analogicznie dla 10.
0
Rozumiem, dziękuję za pomoc. A jeżeli nie jest mniejsza, tylko większa, to nie zamieniamy, tak?