0/1 knapsack DP

0/1 knapsack için DP tablosu kurmayı öğrenirsin.

0/1 knapsack DP

0/1 knapsack için iki boyutlu DP tablosu kurarız. dp[i][w], ilk i eşyayla w kapasite için en yüksek değerdir.

Tablo (n+1) × (W+1) boyutundadır; ilk satır ve sütun sıfırdır.

Her hücre, eşyayı al ya da alma kararının en iyisini saklar.

Hücre bağıntısı

Eğer weights[i-1] ≤ w ise dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]]). Değilse dp[i][w] = dp[i-1][w].

Bu bağıntı, her eşya için al ya da alma kararını net biçimde kodlar.

Sonuç dp[n][W] hücresindedir; tablonun sağ-alt köşesi.

Uygulama Knapsack DP

knap_dp(W, weights, values, n) yaz. 2D DP tablosuyla 0/1 knapsack. print(knap_dp(50, [10, 20, 30], [60, 100, 120], 3)) ile 220 yazdır.

Örnek çözümü göster

def knap_dp(W, weights, values, n):
    # Knapsack DP
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][W]
print(knap_dp(50, [10, 20, 30], [60, 100, 120], 3))

Kendini test et

Alma bağıntısı

take = values[i - 1] + dp[____][w - weights[i - 1]]

Cevabı göster

take = values[i - 1] + dp[i - 1][w - weights[i - 1]]

0/1 knapsack DP: kavramları eşleştir

dp[i][w]

Hücre
take

Al
skip

Alma
max

Büyük
0/1 knapsack DP zaman karmaşıklığı nedir?
- O(n^2)
- O(nW)
- O(W^2)
- O(n + W)
Cevabı göster

O(nW) — O(nW).

Sıradaki ders: Karar tablosu

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler