Optymalny algorytm wydawania reszty z programowaniem dynamicznym – minimalna liczba monet.
Algorytm dynamiczny do wydawania reszty w przeciwieństwie do wersji zachłannej zawsze znajduje optymalne rozwiązanie, niezależnie od zestawu nominałów.
Idea: budujemy tablicę dp, w której dp[i] przechowuje minimalną liczbę monet potrzebnych do wydania kwoty i.
Krok inicjalizacji: dp[0] = 0 (nie potrzeba żadnej monety na kwotę zero), pozostałe komórki ustawiamy na nieskończoność (jeszcze nie wiadomo, czy da się wydać).
Krok przejścia: dla każdej kwoty i od 1 do kwota przeglądamy każdy nominał. Jeśli moneta nie przekracza i, sprawdzamy, czy dp[i - moneta] + 1 daje lepszy wynik niż obecny dp[i]. Jeśli tak – aktualizujemy.
Złożoność O(n · k) wynika z dwóch zagnieżdżonych pętli: zewnętrznej po kwotach, wewnętrznej po nominałach. Algorytm jest wolniejszy od zachłannego, ale zawsze poprawny.
funkcja wydaj_dynamicznie(nominaly, kwota): // dp[i] = minimalna liczba monet do wydania kwoty i dp ← tablica o rozmiarze (kwota + 1) wypełniona nieskończonością dp[0] ← 0 dla i od 1 do kwota: dla każdego nominału moneta w nominaly: jeżeli moneta ≤ i oraz dp[i - moneta] + 1 < dp[i]: dp[i] ← dp[i - moneta] + 1 jeżeli dp[kwota] = nieskończoność: // nie da się wydać tej kwoty zwróć -1 zwróć dp[kwota]
def wydaj_dynamicznie(nominaly, kwota):
nieskonczonosc = float('inf')
dp = [nieskonczonosc] * (kwota + 1)
dp[0] = 0
for i in range(1, kwota + 1):
for moneta in nominaly:
if moneta <= i and dp[i - moneta] + 1 < dp[i]:
dp[i] = dp[i - moneta] + 1
if dp[kwota] == nieskonczonosc:
return -1
return dp[kwota]
# Przykład użycia
print(wydaj_dynamicznie([3, 4], 6))
# Wynik: 2 (czyli 3 + 3)
print(wydaj_dynamicznie([1, 2, 5], 11))
# Wynik: 3 (czyli 5 + 5 + 1)O(n · k)O(k)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: