背包問題：動態規劃的 Hello World#

背包問題是動態規劃領域最經典的問題之一，也是學習 DP 的必經之路。掌握背包問題的解題思路，對於理解動態規劃的核心思想至關重要。

0-1 背包問題#

問題描述#

給你一個可放總重量為 W 的背包和 N 個物品，每個物品有重量 w[i] 和價值 v[i]。現在讓你用這個背包裝物品，問最多能裝的價值是多少？

輸入：W = 5, N = 3
      w = [3, 2, 1], v = [5, 2, 3]
輸出：8
解釋：選擇 i=0 和 i=2 這兩件物品。
      總重量 4 < W，最大價值 = 5 + 3 = 8

為什麼叫 0-1 背包？ 每次只能做兩種選擇：放入當前物品（1）或不放入（0）。 如果每個物品可以放入多個，就變成了完全背包問題。

判斷是否為 DP 問題#

1. 重疊子問題：各種排列組合間存在重複計算
2. 無後效性：選定物品後，重量與價值確定，不受後續影響
3. 最優子結構：後續計算可由前面狀態推導

狀態轉移方程#

狀態定義：DP[tn][rw] 表示考慮前 tn 件物品，背包容量為 rw 時的最大價值

狀態參數：

• tn：已走訪的物品數量
• rw：背包剩餘容量

決策：對於每件物品，選擇「放入」或「不放入」

$$ DP(tn, rw) = \begin{cases} 0, & tn \leq 0 \ 0, & rw \leq 0 \ DP(tn-1, rw), & rw < w[tn] \ \max(DP(tn-1, rw), DP(tn-1, rw-w[tn]) + v[tn]), & rw \geq w[tn] \end{cases} $$

程式碼實作#

fun knapsack01(w: IntArray, v: IntArray, N: Int, W: Int): Int {
    // 創建備忘錄（IntArray 預設即為 0，等同初始化第 0 列/第 0 行）
    val dp = Array(N + 1) { IntArray(W + 1) }

    for (tn in 1..N) {
        for (rw in 1..W) {
            // 第 tn 件物品：陣列 0-indexed，故取 w[tn-1]、v[tn-1]
            if (rw < w[tn - 1]) {
                // 容量不足，不放入
                dp[tn][rw] = dp[tn - 1][rw]
            } else {
                // 決策：放入 vs 不放入
                dp[tn][rw] = maxOf(
                    dp[tn - 1][rw],                          // 不放入
                    dp[tn - 1][rw - w[tn - 1]] + v[tn - 1],  // 放入
                )
            }
        }
    }
    return dp[N][W]
}

備忘錄填充示意#

        rw=0  rw=1  rw=2  rw=3  rw=4  rw=5
tn=0      0     0     0     0     0     0
tn=1      0     0     0     5     5     5
tn=2      0     0     2     5     5     7
tn=3      0     3     3     5     8     8
                              ↑
                        答案：8

完全背包問題#

問題描述#

與 0-1 背包類似，但每種物品可以選擇任意多個。

輸入：W = 5, N = 3
      w = [3, 2, 1], v = [5, 2, 3]
輸出：15
解釋：選擇 i=2 物品 5 次，總價值 = 5 × 3 = 15

關鍵區別#

核心差異

• 0-1 背包：從上一個物品的狀態轉移（tn-1）
• 完全背包：從當前物品的更小容量狀態轉移（tn）

狀態轉移方程#

$$ DP(tn, rw) = \begin{cases} 0, & tn \leq 0 \ 0, & rw \leq 0 \ DP(tn-1, rw), & rw < w[tn] \ \max(DP(tn-1, rw), DP(tn, rw-w[tn]) + v[tn]), & rw \geq w[tn] \end{cases} $$

時間複雜度最佳化#

樸素解法：三重迴圈 O(kv²)

• 走訪物品 × 走訪容量 × 走訪數量

最佳化解法：雙重迴圈 O(kv)

• 將「放幾個」的迴圈隱含在狀態轉移中

fun completeKnapsack(w: IntArray, v: IntArray, N: Int, W: Int): Int {
    val dp = Array(N + 1) { IntArray(W + 1) }

    for (tn in 1..N) {
        for (rw in 1..W) {
            dp[tn][rw] = dp[tn - 1][rw]

            // 關鍵：使用 dp[tn][rw-w] 而非 dp[tn-1][rw-w]
            if (w[tn - 1] <= rw) {
                dp[tn][rw] = maxOf(
                    dp[tn][rw],
                    dp[tn][rw - w[tn - 1]] + v[tn - 1],
                )
            }
        }
    }
    return dp[N][W]
}

空間複雜度最佳化#

由於 DP[tn][rw] 只依賴於 DP[tn-1][rw] 和 DP[tn][...]，可以使用滾動陣列：

計算第 1 個物品時：用第 0 行做 tn-1 的快取，第 1 行做 tn 的快取
計算第 2 個物品時：用第 1 行做 tn-1 的快取，第 0 行做 tn 的快取
...以此類推

fun completeKnapsack(w: IntArray, v: IntArray, N: Int, W: Int): Int {
    val dp = Array(2) { IntArray(W + 1) }  // 只需兩行

    for (tn in 1..N) {
        for (rw in 1..W) {
            val ctn = tn % 2      // 當前行
            val ptn = 1 - ctn     // 上一行

            dp[ctn][rw] = dp[ptn][rw]
            if (w[tn - 1] <= rw) {
                dp[ctn][rw] = maxOf(
                    dp[ctn][rw],
                    dp[ctn][rw - w[tn - 1]] + v[tn - 1],
                )
            }
        }
    }
    return dp[N % 2][W]
}

背包問題的變種#

問題轉化示例：粉碎石頭#

問題：有一堆石頭，每次選兩塊粉碎。若 x ≤ y，結果為 y-x。求最後剩下的最小重量。

轉化思路：

1. 將所有石頭分成兩組
2. 兩組之差就是最終結果
3. 要使差最小，一組應接近總和的 1/2

轉化為背包：

• 背包容量 = 總重量 / 2
• 物品重量 = 石頭重量
• 物品價值 = 石頭重量（價值等於重量）
• 求能裝入的最大價值

背包問題的本質 背包問題的核心是「選擇」——在有限的資源（容量）下，如何選擇物品以達到最優目標（最大價值）。 很多看似不相關的問題，都可以轉化為背包問題。

背包問題總結#

面試提醒 在真正的演算法面試中，很少會直接考察標準背包問題。 面試官更傾向於考察背包問題的變種，需要你識別出背包問題的特徵，並進行轉化。