0/1 knapsack DP
- Algoritmalar kursu
- İleri seviye
- Ders 14/56
- 4 dk
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.
Başlangıç kodu
def knap_dp(W, weights, values, n):
# Knapsack DPÖrnek çözüm
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))Beklenen çıktı
220
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Alma bağıntısı
take = values[i - 1] + dp[____][w - weights[i - 1]]take = values[i - 1] + dp[i - 1][w - weights[i - 1]]Açıklama: i - 1 doğru.
2 0/1 knapsack DP: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
dp[i][w] |
Hücre |
take |
Al |
skip |
Alma |
max |
Büyük |
3 0/1 knapsack DP zaman karmaşıklığı nedir?
- O(n^2)
- O(nW) Doğru cevap
- O(W^2)
- O(n + W)
Açıklama: O(nW).