Karar tablosu

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.

Örnek çözümü göster

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))

Kendini test et

Karar tablosu: kavramları eşleştir

decision

Karar
take

Al
skip

Alma
backtrack

Geri iz
Knapsack DP sonucu hangi hücrede?
- dp[n][W]
- dp[n][0]
- dp[0][0]
- dp[0][W]
Cevabı göster

dp[n][W] — dp[n][W].

Alma kontrolü

if dp[i][w] != dp[____][w]:

Cevabı göster

if dp[i][w] != dp[i - 1][w]:

Sıradaki ders: Özet - Knapsack

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler