Bozuk Para Problemi (Coin Change)

#Nasıl çalışır?

Bozuk para probleminde verilen para birimleriyle bir tutarı en az kaç parayla ödeyebileceğimiz sorulur. Her paradan istediğimiz kadar kullanabiliriz.

Açgözlü yöntem (her seferinde sığan en büyük parayı almak) TL ya da avro gibi gerçek para sistemlerinde doğru sonuç verir, ama her sistemde değil. 1, 3 ve 4'lük paralarla 6 için açgözlü yöntem 4 + 1 + 1 = 3 para kullanır; oysa 3 + 3 = 2 para yeterlidir.

DP her tutarı sırayla çözer: dp[a] = 1 + min(dp[a − c]), yani son kullanılan para c ise geri kalan a − c tutarının en iyi çözümüne bir para eklenir. Hangi paranın seçildiği last[a]'da tutulursa paraların kendisi de geri izlenerek bulunur.

#Kendin dene

#Adım adım

1. 01dp[0] = 0.
2. 02Her a = 1 … A için, a'dan küçük ya da eşit her c parası için dp[a − c] + 1 değerini hesapla.
3. 03En küçüğünü dp[a]'ya, onu veren parayı last[a]'ya yaz.
4. 04A'dan başlayıp last[a] kadar azaltarak kullanılan paraları listele.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

COINS = [1, 3, 4]
INF = float("inf")


def min_coins(amount: int):
    """Returns (fewest coins, the coins used)."""
    dp = [0] + [INF] * amount
    last = [0] * (amount + 1)  # the coin that gave dp[a]
    for a in range(1, amount + 1):
        for c in COINS:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                last[a] = c
    used, a = [], amount
    while a > 0:
        used.append(last[a])
        a -= last[a]
    return dp[amount], used


def greedy(amount: int) -> int:
    """Largest coin first: fast, but not always the fewest."""
    count = 0
    for c in sorted(COINS, reverse=True):
        count += amount // c
        amount %= c
    return count


count, used = min_coins(6)
print(count)
print(" ".join(map(str, used)))  # 3 + 3
print(greedy(6))                 # 4 + 1 + 1: one coin more

#Karmaşıklık

A tutar, k para birimi sayısıdır. Sırt çantası gibi sözde-polinomdur: tutar büyüdükçe tablo büyür. Aynı tablo, döngü sırası değiştirilerek "kaç farklı şekilde ödenir?" sorusunu da yanıtlar.

#Ne zaman kullanılır?

Kasa ve ATM para üstü hesaplama, oyunlarda en az hamleyle bir puana ulaşma ve kaynak birimleriyle bir hedefi en verimli şekilde tamamlama problemleri. Açgözlü yöntemin ne zaman yeterli olduğunu anlamak için iyi bir örnektir.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.