Metoda zachłanna

Powtórzenie: metoda zachłanna, programowanie dynamiczne i grafy - Informatyka - liceum klasa 4, zakres rozszerzony (Python)

Przypomnienie: metoda zachłanna w każdym kroku bierze to, co w tej chwili najlepsze, i nie wraca do decyzji. Przy nominałach 1, 2, 5 reszta wydana największymi monetami jest optymalna, ale przy nominałach 1, 3, 4 kwota 6 zachłannie to 4 + 1 + 1, a lepiej 3 + 3.

def greedy_change(amount, coins):
    result = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            result.append(c)
    return result

print(greedy_change(13, [1, 2, 5]))
print(greedy_change(6, [1, 3, 4]))

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

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