動態規劃入門：一維陣列優化解決 0/1 背包問題

動態規劃入門：一維陣列優化解決 0/1 背包問題

動態規劃 (DP) 是解決多階段決策最優化問題的核心演算法。本文以經典的「數字塔」問題引入 DP 思維，進而深入講解 0/1 背包問題的狀態轉移方程，並展示如何從二維 DP 優化至一維陣列，達到極致時空效率。

動態規劃三大核心特徵

1. 最優子結構：全局最優解包含子問題最優解（數字塔：頂到底最優路徑必含第二層到底最優子路徑）
2. 無後向性：某階段狀態一旦確定，不受後續決策影響
3. 子問題重疊：遞迴解法會重複計算相同子問題，DP 透過記憶化避免

0/1 背包問題定義

有 N 個物品，第 i 個佔體積 need[i]、價值 value[i]。背包容量 V。每個物品只能選 0 或 1 個。求最大總價值。

狀態定義與轉移方程

定義 dp[i][j]：前 i 個物品放入容量 j 的背包最大價值。

if (j < need[i])      // 第 i 件裝不下
    dp[i][j] = dp[i-1][j];
else                  // 取 max(不放, 放入)
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-need[i]] + value[i]);

邊界：dp[0][j] = 0（0 件物品價值為 0）

範例演示

4 件物品：

背包容量 V=5。填表過程：

i\j  0  1  2  3  4  5
0    0  0  0  0  0  0
1    0  0  2  2  2  2
2    0  0  2  5  5  7
3    0  0  2  5  5  7
4    0  2  2  5  7  7

答案：dp[4][5] = 7（選物品 2+4，體積 3+1=4，價值 5+2=7）

空間優化演進

階段 1：二維陣列 O(NV)

int dp[N+1][V+1];
for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= V; ++j)
        dp[i][j] = (j < need[i]) ? dp[i-1][j]
                                 : max(dp[i-1][j], dp[i-1][j-need[i]] + value[i]);

階段 2：滾動陣列 O(2V) → O(V)

觀察轉移方程：dp[i][*] 僅依賴 dp[i-1][*]。只需兩行交替：

int dp[2][V+1];
for (int i = 1; i <= N; ++i) {
    int cur = i & 1, prev = cur ^ 1;
    for (int j = 1; j <= V; ++j)
        dp[cur][j] = (j < need[i]) ? dp[prev][j]
                                   : max(dp[prev][j], dp[prev][j-need[i]] + value[i]);
}

階段 3：一維陣列逆序遍歷 O(V) —— 終極優化

int dp[V+1] = {0};
for (int i = 1; i <= N; ++i)
    for (int j = V; j >= need[i]; --j)  // 關鍵：從大到小！
        dp[j] = max(dp[j], dp[j - need[i]] + value[i]);

為什麼必須逆序？

dp[j] 依賴同一輪的 dp[j - need[i]]（舊值）。順序遍歷會提前覆蓋舊值，導致同一物品被重複放入（變成完全背包）。逆序保證讀到的 dp[j - need[i]] 仍是上一輪（i-1）的值。

完整可執行程式

#include <stdio.h>
#include <stdlib.h>

#define MAX(a,b) ((a)>(b)?(a):(b))

int main() {
    int n = 4, V = 5;
    int need[] = {0, 2, 3, 4, 1};   // 1-based
    int value[] = {0, 2, 5, 3, 2};

    int dp[V+1] = {0};

    for (int i = 1; i <= n; ++i) {
        for (int j = V; j >= need[i]; --j) {
            dp[j] = MAX(dp[j], dp[j - need[i]] + value[i]);
        }
    }

    printf("最大價值: %d\n", dp[V]);  // 輸出 7
    return 0;
}

複雜度總結

延伸：完全背包與多重背包

• 完全背包：物品無限件，內層循環 順序 遍歷 j = need[i] to V
• 多重背包：物品有限件，二進制拆分轉化為 0/1 背包，或單調佇列優化