0/1 背包問題

https://www.hello-algo.com/zh-hant/chapter_dynamic_programming/knapsack_problem/#__tabbed_4_6

1. 問題定義

給定 (Given):
- \(n\) 個物品 (items)。
- 每個物品 \(i\) 有一個重量 \(w_i\) 和一個價值 \(v_i\)。
- 一個背包，其最大可承受重量 (容量) 為 \(W\)。
限制 (Constraint):
- 對於每個物品，你只能選擇 拿 (1) 或 不拿 (0)。
- 不能只拿物品的一部分（這與「部分背包問題」Fractional Knapsack Problem 不同）。
目標 (Goal):
- 求解在總重量不超過 \(W\) 的前提下，能放入背包的最大總價值。

筆記重點：

Greedy (貪婪法) 無法保證得到 0/1 背包問題的最佳解。

此問題具有最佳子結構 (Optimal Substructure)，適合使用 DP 求解。

2. Recursive Form (遞迴關係式)

我們使用一個二維陣列（表格）\(C[i, k]\) 來定義子問題：

\(C[i, k]\) = 考慮前 \(i\) 個物品 (item 1 到 \(i\))，在背包容量上限為 \(k\) 時，所能得到的最大總價值。

我們的目標是求出 \(C[n, W]\)。

遞迴推導：

當我們考慮第 \(i\) 個物品（其重量為 \(w_i\)，價值為 \(v_i\)）時，有兩種選擇：

不放第 \(i\) 個物品：
- 這可能是因為不想放，或是因為放不下 (\(k < w_i\))。
- 最大價值會等於「只考慮前 \(i-1\) 個物品，且容量為 \(k\)」時的最大價值。
- 即 \(C[i-1, k]\)。
放第 \(i\) 個物品：
- 這必須在 \(k \ge w_i\) (容量足夠) 的前提下才能發生。
- 總價值會等於「第 \(i\) 個物品的價值 \(v_i\)」加上「考慮前 \(i-1\) 個物品，且容量剩下 \(k - w_i\)」的最大價值。
- 即 \(v_i + C[i-1, k - w_i]\)。

關係式總結：

\(C[i, k]\) 就是取上述兩種情況中，價值較大的一個。

\[C[i, k] = \begin{cases} 0 & \text{if } i = 0 \text{ or } k = 0 \\ C[i-1, k] & \text{if } k < w_i \text{ (放不下第 i 個物品)} \\ \max(C[i-1, k], \quad v_i + C[i-1, k - w_i]) & \text{if } k \ge w_i \text{ (可選擇放或不放)} \end{cases}\]

3. 演算法 (Algorithm) - Bottom-up DP

我們可以使用「由下而上」(Bottom-up) 的方式，填滿 \(C[i, k]\) 這個表格來求解。

程式碼片段

// 演算法：0/1 Knapsack
// 輸入: n (物品數量), W (總容量), v (價值陣列), w (重量陣列)
// 輸出: 最大價值

// 1. 建立一個 (n+1) x (W+1) 的表格 C
create table C[0..n, 0..W]

// 2. 初始化 Base Case (第 0 列)
// 當沒有物品(i=0)時，任何容量 k 的價值都是 0
for k <- 0 to W:
    C[0, k] <- 0

// 3. 迭代所有物品 i (從 1 到 n)
for i <- 1 to n:
    // 初始化 Base Case (第 0 行)
    // 當容量為 0 (k=0)時，任何物品 i 都放不進，價值為 0
    C[i, 0] <- 0

    // 4. 迭代所有容量 k (從 1 到 W)
    for k <- 1 to W:
        // 取得第 i 個物品的價值 v_i 和重量 w_i
        
        // 情況 1: 當前容量 k < 物品 i 的重量
        if k < w_i:
            // 放不下，價值等於「不放」的情況
            C[i, k] <- C[i-1, k]
        
        // 情況 2: 當前容量 k >= 物品 i 的重量
        else:
            // 比較「不放」和「放」哪個價值高
            C[i, k] <- max(
                            C[i-1, k],                  // 不放第 i 個物品
                            v_i + C[i-1, k - w_i]       // 放第 i 個物品
                        )

// 5. 最終答案
// 考慮了全部 n 個物品，且總容量為 W 時的最大價值
return C[n, W]

4. 複雜度分析 (Complexity Analysis)

時間複雜度 (Time Complexity): \(O(nW)\)
- 原因： 來自兩個巢狀迴圈 (nested loop)。外層迴圈跑 \(n\) 次 (for \(i\))，內層迴圈跑 \(W\) 次 (for \(k\))。
空間複雜度 (Space Complexity): \(O(nW)\)
- 原因： 需要一個 \(C[0..n, 0..W]\) 的二維表格來儲存子問題的解，表格大小為 \((n+1) \times (W+1)\)，也就是額外花費的記憶體。

填表過程

直觀的說

1. 裝得下嗎？ (\(k < w_i\))

不行： 答案 = 抄樓上 (\(C[i-1, k]\))

2. 裝得下。 (\(k \ge w_i\))

答案 = 比較下面兩者，選大的：
- 不拿： 樓上 (\(C[i-1, k]\))
- 拿： \(\text{斜上} + \text{新價值}\) (\(C[i-1, k - w_i] + v_i\))

「斜上」 就是指：往上一列，再往左 \(w_i\) 格。

物品 1：\(i=1, w_1=2, v_1=6\)

\(C[1,k]=\max{C[0,k],6+C[0,k-2]}\)

結果列：

\(C[1,k]\)	0	1	2	3	4	5
值	0	0	6	6	6	6

物品 2：\(i=2, w_2=3, v_2=10\)

\(C[2,k]=\max{C[1,k],;10+C[1,k-3]}\)

結果列：

\(C[2,k]\)	0	1	2	3	4	5
值	0	0	6	10	10	16

物品 3：\(i=3, w_3=4, v_3=12\)

\(C[3,k]=\max{C[2,k],12+C[2,k-4]}\)

最終列：

\(C[3,k]\)	0	1	2	3	4	5
值	0	0	6	10	12	16

完整表格

\(C[i,k]\)	2	3	4	5
\(i=0\)	0	0	0	0
\(i=1\)	6	6	6	6
\(i=2\)	6	10	10	16
\(i=3\)	6	10	12	16

答案：\(C[n,W]=C[3,5]=16\)

回溯解集合

從 \(C[3,5]=16\) 往回：

\(C[3,5]=16= C[2,5]\) ⇒ 不選物品 3。移到 \((2,5)\)
\(C[2,5]=16 \ne C[1,5]=6\) ⇒ 選物品 2。\(k\leftarrow 5-3=2\)，移到 \((1,2)\)
\(C[1,2]=6 \ne C[0,2]=0\) ⇒ 選物品 1。\(k\leftarrow 2-2=0\)，移到 \((0,0)\) 結束

選擇：\({1,2}\)
總重量：\(2+3=5\)
總價值：\(6+10=16\)