Algoritmalar
tr

Bozuk Para

Dinamik Programlama O(n · amount) O(n · amount)

Her birimden sınırsız bulunduğunda, hedef tutara ulaşan en az sayıda bozuk para.

c\a0123456
∅·······
1·······
3·······
4·······
Paralar134tutar 6
1/57

0 tutarının maliyeti yok.

Değişmezdp[i][a], ilk i para biriminden a tutarını oluşturan en az para sayısıdır (oluşturulamıyorsa ∞).

coin-change.c
#define INF 1000000
 
int min(int a, int b) { return a < b ? a : b; }
 
int coinChange(int coins[], int n, int amount) {
    int dp[n + 1][amount + 1];
 
    for (int i = 0; i <= n; i++) {
        for (int a = 0; a <= amount; a++) {
            if (a == 0)
                dp[i][a] = 0;
            else if (i == 0)
                dp[i][a] = INF;
            else if (coins[i - 1] > a)
                dp[i][a] = dp[i - 1][a];
            else
                dp[i][a] = min(dp[i - 1][a],
                               dp[i][a - coins[i - 1]] + 1);
        }
    }
    return dp[n][amount];
}

Bozuk Para nasıl çalışır?

dp[i][a] = ilk i birimle a tutarı için en az para: parayı atla ya da bir kez kullanıp aynı satırda kal (sınırsız arz). ∞ ulaşılamaz tutarları işaretler.

Ne zaman kullanılır?

Para üstü, en az kaynakla kombinasyon; sınırsız sırt çantası problemlerinin şablonu.