Kiedy metoda zachłanna zawodzi

Metoda zachłanna - Algorytmy: zakres rozszerzony (Python)

Dla polskich nominałów zachłanne wydawanie zawsze daje najmniej monet. Nie jest to jednak prawda dla każdego zestawu. Dla monet 1, 3 i 4 kwotę 6 metoda zachłanna wydaje jako 4 + 1 + 1 (trzy monety), a wystarczą dwie: 3 + 3. Najlepsze rozwiązanie dla dowolnych nominałów daje programowanie dynamiczne (osobny temat).

coins = [4, 3, 1]
amount = 6
used = []
for coin in coins:
    while amount >= coin:
        amount -= coin
        used.append(coin)
print("zachłannie:", used, "monet:", len(used))
print("najlepiej: [3, 3] monet: 2")

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

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.