Algorytm zachłanny

0

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...

title

title

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?

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0