算法精講：01 背包問題三種動態規劃視角與空間優化 C/C++ 實現

算法精講：01 背包問題三種動態規劃視角與空間優化 C/C++ 實現

01 背包是動態規劃入門的「你好世界」。本文從「正向遞推」「逆向遞推」「記憶化搜索」三種 DP 視角，推導遞推關係，並給出二維表、一維滾動數組兩種空間實現，附帶完整 C/C++ 代碼與複雜度分析。

問題形式化

• 輸入：n 件物品，第 i 件重量 w[i]、價值 v[i]；背包容量 W
• 約束：每件物品最多選 1 件（0 或 1）
• 目標：最大化總價值，總重量 ≤ W

三種 DP 視角統一建模

視角 1：正向遞推（從小規模構建大規模）

定義：dp[i][j] = 前 i 件物品裝入容量 j 的最大價值

遞推：

// 第 i 件不選 / 選
dp[i][j] = max( dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1] )  // j ≥ w[i-1]
dp[i][j] = dp[i-1][j]                                        // j < w[i-1]

初始：dp[0][j] = 0（無物品價值為 0）

答案：dp[n][W]

視角 2：逆向遞推（從大規模分解到小規模）

定義：dp[i][j] = 從第 i 件開始考慮，剩餘容量 j 的最大價值

遞推：

for (int i = n-1; i >= 0; i--) {
    for (int j = 0; j <= W; j++) {
        if (j < w[i]) dp[i][j] = dp[i+1][j];
        else dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
    }
}
// 答案：dp[0][W]

優勢：天然支持「從第 k 件開始」的子問題查詢。

視角 3：記憶化搜索（自頂向下 + 緩存）

int memo[MAX_N][MAX_W];
bool vis[MAX_N][MAX_W];

int dfs(int i, int j) {  // 從第 i 件開始，容量 j
    if (i == n) return 0;
    if (vis[i][j]) return memo[i][j];
    
    int res = dfs(i+1, j);  // 不選
    if (j >= w[i]) 
        res = max(res, dfs(i+1, j-w[i]) + v[i]);  // 選
    
    vis[i][j] = true;
    return memo[i][j] = res;
}
// 調用：dfs(0, W)

優勢：只計算到達的狀態，稀疏問題效率更高。

代碼實現：二維表版（教學標準）

#include <stdio.h>
#include <string.h>
#include <algorithm>

#define MAX_N 100
#define MAX_W 10000

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N + 1][MAX_W + 1];

void solve_2d() {
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= w[i-1]) {
                dp[i][j] = std::max(dp[i][j], dp[i-1][j - w[i-1]] + v[i-1]);
            }
        }
    }
    printf("result = %d\n", dp[n][W]);
}

代碼實現：一維滾動數組版（生產標準 O(W) 空間）

#include <stdio.h>
#include <string.h>
#include <algorithm>

#define MAX_N 100
#define MAX_W 10000

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_W + 1];

void solve_1d() {
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i < n; i++) {
        // 關鍵：逆序遍歷！
        for (int j = W; j >= w[i]; j--) {
            dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    printf("result = %d\n", dp[W]);
}

逆序遍歷數學證明：為什麼 01 背包必須逆序？

一維數組 dp[j] 存儲「處理到前 i 件物品時」容量 j 的最大值。

• 正序：計算 dp[j] 時，dp[j-w[i]] 已被本輪更新（包含第 i 件），導致同一物品被多次選取 → 退化為完全背包
• 逆序：計算 dp[j] 時，dp[j-w[i]] 仍是上一輪值（未含第 i 件），保證每件至多選一次

測試樣例驗證

int main() {
    n = 4; W = 5;
    int w1[] = {2, 1, 3, 2};
    int v1[] = {3, 2, 4, 2};
    memcpy(w, w1, sizeof(w1));
    memcpy(v, v1, sizeof(v1));
    
    solve_2d();  // result = 7
    solve_1d();  // result = 7
    return 0;
}

路徑重構：輸出選取的物品索引

// 二維版路徑重構
int i = n, j = W;
while (i > 0) {
    if (dp[i][j] != dp[i-1][j]) {
        printf("Selected item %d (w=%d, v=%d)\n", i, w[i-1], v[i-1]);
        j -= w[i-1];
    }
    i--;
}

// 一維版需額外記錄選擇路徑（或重跑二維表）

複雜度與選型決策表

擴展變體速覽

• 輸出方案數：dp[j] += dp[j-w[i]]（計數 DP，注意大數取模）
• 輸出具體方案：DFS 回溯 + 剪枝
• 分組背包：每組互斥，內層循環遍歷組內物品
• 多重背包：二進制拆分 k = 1,2,4,... 轉 01 背包
• 依賴背包：拓撲序 DP

01 背包的三種 DP 視角本質上是同一遞推關係的不同遍歷順序。掌握「正向構建 vs 逆向分解 vs 遞歸緩存」的思維轉換，並熟練駕馭一維滾動數組的逆序遍歷邏輯，是攻克所有背包族問題的核心內功。