0/1 背包問題

2021-06-26 00:47:58 +0800 CST Tags: dp, knapsack

問題：給定一個限重 $W$ 的背包以及 $N$ 個重量、價值分別為 w[i]、v[i] 的物品 i，請問要怎麼把這些物品在容量限制內放進背包裡才能使得背包裡的物品總價值最大？

解法：考慮子問題 dp$_i[w]$ 為當候選物品為 1 到 $i$ 的時候，在背包限重縮水為 $w$ 的情況下所能承裝物品的最大總價值，那麼易知本題答案為 dp$_N[W]$。如何遞迴地計算子問題？只要掌握住 dp$_i[w] = \max\big\{$ dp$_{i-1}[w],$ dp$_{i-1}\big[w\ -$ w$[i]\big] +$ v$[i]\ \big\}$ 這個原理即可，它的意思是說對於 $w$ 這個限重而言，在只能挑選第 1 到 $i$ 個物品的限制下如果確定不選物品 $i$，那它對應到的最大價值自然就會跟只考慮第 1 到 $i-1$ 個物品之下的同限重是一樣的；如果確定入選物品 $i$，那麼它對應到的最大價值扣掉 v$[i]$ 後自然就會是在只考慮第 1 到 $i-1$ 個物品之下的 $w\ -$ w[$i$] 這個限重所對應到的最大價值，這兩個 case 裡面挑一個比較大的就是答案。雖然這題的遞迴式是 top-down 地寫，但實作的時候用 bottom-up 會比較方便，另外在更新一個完整回合的 dp 的時候還有一個小技巧，就是由於一個限重的更新都只會用到前一個回合等重或較小的限重，所以必須按照由重到輕的順序才能 in-place 更新，才能確保任意時刻 dp 的較重部分屬第 $i$ 回合，較輕部分屬第 $i-1$ 回合而不相衝。

效能：空間複雜度 $\mathcal O(W)$、時間複雜度 $\mathcal O(NW)$。

附註：
[1] https://web.ntnu.edu.tw/~algo/KnapsackProblem.html#3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int n, W; // n := 物品數量、W := 背包限重
int dp[W+1]; // dp[w] := 已知物品 1 ~ (i-1) 之中我們已選入總重「不超過」w 的物品放進背包時所能產生的最大價值
                 // 更新後變成已知物品 1 ~ i 之中我們已選入總重「不超過」w 的物品放進背包時所能產生的最大價值
                 // 一開始須歸零
while (n--) {
    int w, v; cin >> w >> v; // 輸入每個物品的重量與價值
    for (int i=W; i>=w; i--) // 由重到輕的順序才能 in-place 更新
        if (dp[i-w] + v > dp[i])
            dp[i] = dp[i-w] + v;
}

// 最大化背包內的物品總價值
cout << dp[W] << '\n';