動態規劃完全背包問題 C 語言實現：O(nW) 空間優化與代碼詳解

問題描述

有 n 種物品，第 i 種重量 w[i]、價值 v[i]，**每種可無限選擇**。背包容量 W，求最大價值總和。

狀態定義

dp[i][j]：前 i 種物品，容量 j 時的最大價值。

遞推方程

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]) （若 j >= w[i]）

• 不選第 i 種：dp[i-1][j]
• 選第 i 種：**仍可再選**，故狀態轉移自 dp[i][j-w[i]]（關鍵差異：01 背包用 dp[i-1][j-w[i]]）

二維數組實現 O(nW) 時間、O(nW) 空間

#include 
#include 

#define MAX_N 100

int n = 4, W = 5;
int w[MAX_N] = {2, 1, 3, 2};
int v[MAX_N] = {3, 2, 4, 2};
int dp[MAX_N+1][MAX_N+1];

int main() {
    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] = dp[i][j] > dp[i][j-w[i-1]] + v[i-1] ? dp[i][j] : dp[i][j-w[i-1]] + v[i-1];
        }
    }
    printf("Max value = %d\n", dp[n][W]); // 10
    return 0;
}

一維數組優化 O(W) 空間

**正序遍歷** 容量（01 背包為逆序）：

int dp[MAX_N+1] = {0};
for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= W; j++) { // 正序！
        if (dp[j] < dp[j-w[i]] + v[i])
            dp[j] = dp[j-w[i]] + v[i];
    }
}
printf("Max value = %d\n", dp[W]); // 10

完整可運行代碼（含路徑追蹤）

#include 
#include 

#define MAX_N 100

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N+1];
int choice[MAX_N+1]; // 記錄最後選擇的物品

void solve() {
    memset(dp, 0, sizeof(dp));
    memset(choice, -1, sizeof(choice));
    for (int i = 0; i < n; i++) {
        for (int j = w[i]; j <= W; j++) {
            if (dp[j] < dp[j-w[i]] + v[i]) {
                dp[j] = dp[j-w[i]] + v[i];
                choice[j] = i; // 記錄選了第 i 種
            }
        }
    }
    // 回溯輸出方案
    int cur = W;
    printf("選擇方案：");
    while (cur > 0 && choice[cur] != -1) {
        int idx = choice[cur];
        printf("物品%d(w=%d,v=%d) ", idx, w[idx], v[idx]);
        cur -= w[idx];
    }
    printf("\n最大價值：%d\n", dp[W]);
}

int main() {
    n = 3; W = 7;
    int ww[] = {3,4,2}, vv[] = {4,5,3};
    memcpy(w, ww, sizeof(ww));
    memcpy(v, vv, sizeof(vv));
    solve();
    return 0;
}

複雜度總結

關鍵點總結

1. **完全背包 = 正序遍歷容量**（允許重複選擇）
2. **01 背包 = 逆序遍歷容量**（每種至多一件）
3. 狀態壓縮後無法直接回溯，需額外 `choice` 數組記錄決策
4. 初始化 `dp[0]=0`，其餘 0 即可（價值非負）

總結

完全背包是動態規劃經典模型。**一維正序遍歷**是空間優化核心技巧，工程首選。理解「狀態轉移來源」區別（`dp[i][j-w]` vs `dp[i-1][j-w]`）是區分 01/完全/多重背包的關鍵。代碼模板化後，可快速解決「硬幣找零」「換錢最少硬幣數」「背包最大價值」等實際問題。