Nominały 1, 3 i 4

Kiedy metoda zachłanna zawodzi: kontrprzykład - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

Metoda zachłanna nie zawsze daje najlepszy wynik. Dla nominałów `1, 3, 4` i kwoty 6 zachłannie bierzemy `4 + 1 + 1` (trzy monety), a wystarczą dwie: `3 + 3`. Taki przypadek to **kontrprzykład**: jeden przykład wystarczy, żeby obalić twierdzenie "metoda zachłanna zawsze daje najmniej monet".

def greedy(amount, coins):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count

print("zachłannie:", greedy(6, [1, 3, 4]))
print("najlepiej: 2 (3 + 3)")

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 3, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.