Karar tablosu
- Algoritmalar kursu
- İleri seviye
- Ders 15/56
- 4 dk
Her eşya için al ya da alma kararı tabloya yazmayı öğrenirsin.
Karar tablosu
DP tablosu, her eşya için 'al' ya da 'alma' kararını saklar. Sonuç dp[n][W]'de, en yüksek değerdedir.
Tablo, hangi eşyaların seçildiğini bulmak için de kullanılabilir; geri izleme yapılır.
Bu yüzden knapsack DP'si yalnızca değer değil, kararları da saklar.
Eşya seçimi
Geri izlemeyle hangi eşyaların alındığı bulunur: dp[i][w] ≠ dp[i-1][w] ise eşya i alınmıştır.
Bu, yalnızca en yüksek değeri değil, hangi eşyaların o değeri verdiği de söyler.
Pratikte, yatırım kararlarında hangi varlıkların seçileceğini gösterir.
Uygulama Knapsack seçim
knap_items(W, weights, values, n) yaz. DP + geri izlemeyle alınan eşya indekslerini döndür. print(knap_items(50, [10, 20, 30], [60, 100, 120], 3)) ile [2, 3] yazdır.
Başlangıç kodu
def knap_items(W, weights, values, n):
# Knapsack seçimÖrnek çözüm
def knap_items(W, weights, values, n):
# Knapsack seçim
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]
items = []
i, w = n, W
while i > 0 and w > 0:
if dp[i][w] != dp[i - 1][w]:
items.append(i)
w -= weights[i - 1]
i -= 1
return sorted(items)
print(knap_items(50, [10, 20, 30], [60, 100, 120], 3))Beklenen çıktı
[2, 3]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Karar tablosu: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
decision |
Karar |
take |
Al |
skip |
Alma |
backtrack |
Geri iz |
2 Knapsack DP sonucu hangi hücrede?
- dp[n][W] Doğru cevap
- dp[n][0]
- dp[0][0]
- dp[0][W]
Açıklama: dp[n][W].
3 Alma kontrolü
if dp[i][w] != dp[____][w]:if dp[i][w] != dp[i - 1][w]:Açıklama: i - 1 doğru.