0/1 Sırt Çantası

Dinamik Programlama O(n · W) O(n · W)

Bir ağırlık sınırı altında toplam değeri en büyükler; her öğe için al ya da bırak kararını verir.

i\c	0	1	2	3	4	5
∅	0	·	·	·	·	·
#1	·	·	·	·	·	·
#2	·	·	·	·	·	·
#3	·	·	·	·	·	·

Öğelerw1·v6w2·v10w3·v12kap. 5

1/25

Taban durum (eşya yok veya kapasite yok) → dp[0][0] = 0.

Değişmezdp[i][c], yalnızca ilk i eşyayı kullanarak c kapasitesinde elde edilen en yüksek değerdir.

hesaplanıyorokuduğudolu

knapsack.c

int max(int a, int b) { return a > b ? a : b; }
 
int knapsack(int w[], int val[], int n, int W) {
    int dp[n + 1][W + 1];
 
    for (int i = 0; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            if (i == 0 || c == 0)
                dp[i][c] = 0;
            else if (w[i - 1] > c)
                dp[i][c] = dp[i - 1][c];
            else
                dp[i][c] = max(dp[i - 1][c],
                    dp[i - 1][c - w[i - 1]] + val[i - 1]);
        }
    }
    return dp[n][W];
}

0/1 Sırt Çantası nasıl çalışır?

Her öğe ve kapasite için iki dünyanın iyisini tut: öğeyi atla ya da al ve değerini kalan kapasitenin en iyi sonucuna ekle. Tablo her alt yanıtı yeniden kullanır.

Ne zaman kullanılır?

Öğelerin bölünemediği bütçeli seçim problemleri: kargo, proje portföyleri, stok kesimi.