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$