0/1 Sırt Çantası (Knapsack)

#Nasıl çalışır?

0/1 sırt çantası (knapsack) probleminde her eşyanın bir ağırlığı ve değeri vardır; çantanın taşıyabileceği ağırlık sınırlıdır. Her eşya ya alınır ya alınmaz (0/1) ve toplam değer en yükseğe çıkarılmak istenir.

Açgözlü yaklaşım (ör. değer/ağırlık oranı en yüksek olanı almak) bu problemde yanılabilir. Tüm alt kümeleri denemek ise 2ⁿ seçenek demektir.

DP tablosunda dp[i][c], ilk i eşyayı kullanarak c kapasiteyle elde edilebilecek en yüksek değerdir. Her hücre için iki seçenek vardır: i. eşyayı almamak (dp[i − 1][c]) ya da sığıyorsa almak (dp[i − 1][c − w] + v). Büyük olan yazılır.

Tablo dolduktan sonra sağ alttan geri yürünür: bir hücre üstündekinden farklıysa o eşya alınmıştır.

#Kendin dene

#Adım adım

1. 01dp[0][c] = 0: hiç eşya yokken değer 0.
2. 02Her eşya i (ağırlık w, değer v) ve her kapasite c için: almamak dp[i − 1][c].
3. 03w ≤ c ise almak dp[i − 1][c − w] + v; ikisinden büyüğünü dp[i][c]'ye yaz.
4. 04dp[n][W] cevaptır; seçilen eşyaları bulmak için sağ alttan geri izle.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

# (weight, value) of each item.
ITEMS = [(1, 1), (3, 4), (4, 5), (5, 7)]
W = 7

n = len(ITEMS)
# dp[i][c] = best value using the first i items with capacity c.
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    w, v = ITEMS[i - 1]
    for c in range(W + 1):
        dp[i][c] = dp[i - 1][c]  # skip item i
        if w <= c:
            dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)  # or take it

# Walk back: a value that differs from the row above means item i was taken.
taken, c = [], W
for i in range(n, 0, -1):
    if dp[i][c] != dp[i - 1][c]:
        taken.append(i)
        c -= ITEMS[i - 1][0]

print(dp[n][W])
print(" ".join(map(str, reversed(taken))))  # 1-based item numbers

#Karmaşıklık

n eşya sayısı, W kapasitedir. O(n · W) polinom gibi görünse de W'nin sayısal değerine bağlıdır (sözde-polinom): kapasite çok büyükse tablo da büyür. Tek satırlık bir diziyle, kapasiteyi büyükten küçüğe dolaşarak bellek O(W)'ye indirilebilir.

#Ne zaman kullanılır?

Bütçe ve kaynak dağıtımı, yatırım portföyü seçimi, kargo yükleme, sınav için konu seçimi gibi "sınırlı kapasiteyle en çok değeri seç" problemleri. Aynı tablo fikri alt küme toplamı (subset sum) ve bozuk para problemlerinde de kullanılır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Bozuk Para Problemi (Coin Change)
• Kesirli Sırt Çantası