【演算法】0/1 背包問題（Knapsack Problem）

發布於 更新於 分類於 ， 閱讀次數： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘

簡介

發明 DP 的真是個天才、注意看，這個會 DP 的男人太狠了

0/1 背包問題的題目在於物品的放或不放，並且在有限重量的背包中，獲得最高價值。

通常可以想到用暴力（就是數學 n 個物品取或不取的兩種可能），但是 O(2n)O(2^n) 真的很恐怖，資料一多，馬上 TLE。

因此利用陣列紀錄每個物品在某重量該放與不放，可以紀錄之前的資料又不會重新計算。

原理

假設你的背包可以放 10Kg，物品如下：

Weight Value
Item A 5 4
Item B 1 2
Item C 3 3
Item D 4 6

這些物品在背包內可以利用動態規劃，找出可容納的最大價值。

以二維的 DP 為例，要執行它，我們要先定義幾件事情：

int dp[i][j]

  1. i 表示第 i 件物品
  2. j 表示背包為 j 重量時

所以你的程式碼應該像是這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n = 4;                     // 4 items
int m = 10;                    // 10kg bag
int item_w[4] = {5, 1, 3, 4};  // item weight
int item_v[4] = {4, 2, 3, 6};  // item value

// init
// Remind: dp[0][] must be 0, cause it has no item
int dp[n + 1][m + 1];
for (int i = 0; i < m + 1; i++) dp[0][i] = 0;

// DP
for (int i = 1; i <= n; i++) {  // From the first item starts
    for (int j = 0; j < m + 1; j++) {
        ...
    }
}

以上是初始化的步驟，接著，我們就可以來判斷和計算了。

首先我們要知道的點是：i 表示物品、j 表示重量

轉換成陣列即是：

j(weight) 0 1 2 3 4 5 6 7 8 9 10
i(Item) 0 0 0 0 0 0 0 0 0 0 0

當我們放入 Item A（W:5 V:4） 時：

j(weight) 0 1 2 3 4 5 6 7 8 9 10
i(Item) = 0 0 0 0 0 0 0 0 0 0 0 0
i(A) = 1 0 0 0 0 0 4 4 4 4 4 4

可以看到當 j = 5 時，我們才放進包包。OK，這裡沒有需要判斷的地方，應該沒什麼問題。

當我們放入 Item B（W:1 V:2） 時：

j(weight) 0 1 2 3 4 5 6 7 8 9 10
i(Item) = 0 0 0 0 0 0 0 0 0 0 0 0
i(A) = 1 0 0 0 0 0 4 4 4 4 4 4
i(B) = 2 0 2 2 2 2 4 6 6 6 6 6

uhh，出現了有趣的地方，尤其是 j = 4~6 的部分。

這裡就出現了需要判斷的地方，我們要判斷的東西就是我們要放還是不放？

我們知道 j = 1 時可以放 Item B，是因為前面的物品沒有放進包包所以不用看出怎麼判斷。

但是當我們遇到 j = 5 時，就要判斷：
(1). 我們是否可放？
(2). 放了是否小於原本的價值？

照這個判斷，我們可以寫出：

若放不了，

1
2
3
4
5
if (j >= item_w[i - 1]) {  // (1). if bag weight is equal or bigger than item weight
    ...
} else {
    ...
}

而 (2). 放了是否大於原本的價值？這個問題就涉及到了上個 Item 在包包的狀態，也就是 i - 1。

我們可以得出：

1
2
3
4
5
if (dp[i - 1][j - item_w[i - 1]] + item_v[i - 1] > dp[i - 1][j]) {
    dp[i][j] = dp[i - 1][j - item_w[i - 1]] + item_v[i - 1];
} else {
    dp[i][j] = dp[i - 1][j];
}

剩下的就是重複步驟。Item C(W: 3, V: 3)

j(weight) 0 1 2 3 4 5 6 7 8 9 10
i(Item) = 0 0 0 0 0 0 0 0 0 0 0 0
i(A) = 1 0 0 0 0 0 4 4 4 4 4 4
i(B) = 2 0 2 2 2 2 4 6 6 6 6 6
i(C) = 3 0 2 2 3 5 5 6 6 7 9 9

Item D(W: 4, V: 6)

j(weight) 0 1 2 3 4 5 6 7 8 9 10
i(Item) = 0 0 0 0 0 0 0 0 0 0 0 0
i(A) = 1 0 0 0 0 0 4 4 4 4 4 4
i(B) = 2 0 2 2 2 2 4 6 6 6 6 6
i(C) = 3 0 2 2 3 5 5 6 6 7 9 9
i(D) = 4 0 2 2 3 6 8 8 9 11 11 12

此時 dp[n][m] 即為解答，當問題縮小時，亦可直接找到答案：如詢問當背包上限為 8kg 時，答案即為 11

完整程式碼

二維版（上述原理）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int n = 4;                     // 4 items
int m = 10;                    // 10kg bag
int item_w[4] = {5, 1, 3, 4};  // item weight
int item_v[4] = {4, 2, 3, 6};  // item value

// init
// Remind: dp[0][] must be 0, cause it has no item
int dp[n + 1][m + 1];
for (int i = 0; i < m + 1; i++) dp[0][i] = 0;

// DP
for (int i = 1; i <= n; i++) {  // From the first item starts
    for (int j = 0; j < m + 1; j++) {
        if (j >= item_w[i - 1]) {  // (1). if bag weight is equal or bigger than item weight
            // u can use max()
            // 1.
            if (dp[i - 1][j - item_w[i - 1]] + item_v[i - 1] > dp[i - 1][j]) {
                dp[i][j] = dp[i - 1][j - item_w[i - 1]] + item_v[i - 1];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
            // or 2. 
            // dp[i][j] = max(dp[i - 1][j - item_w[i - 1]] + item_v[i - 1], dp[i - 1][j]);
        } else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}

// output
cout << dp[n][m];

一維版

交互陣列版

問題

  • ZeroJudge b184. 5. 裝貨櫃問題