01 背包是經典動態規劃問題。本文提供遞歸回溯基礎實現、狀態空間樹分析、備忘錄優化、動態規劃底向上實現、空間優化版本，完整覆蓋從指數級到多項式級的演進路徑。
n 件物品，重量 w[i]，價值 v[i]；背包容量 CC#include
#include
#define MAX_N 20
int w[MAX_N], v[MAX_N], choose[MAX_N];
int n, C, best_value = 0;
int best_choose[MAX_N];
// 遞歸搜索：考慮第 idx 件物品，剩余容量 rest
void dfs(int idx, int rest, int cur_value) {
if (idx == n) { // 葉子節點
if (cur_value > best_value) {
best_value = cur_value;
for (int i=0; i idx=0
/ \
不裝 裝 (w[0]≤C)
/ \ / \
... ... ... ...
深度 n，每層 2 分支 → 2^n 葉子節點
時間複雜度：O(2^n) - 指數級，n>30 不可行狀態定義：memo[idx][rest] = 從 idx 開始、剩余容量 rest 可獲得的最大價值
int memo[MAX_N][MAX_C+1]; // -1 表示未計算
int visited[MAX_N][MAX_C+1];
int dfs_memo(int idx, int rest) {
if (idx == n) return 0;
if (visited[idx][rest]) return memo[idx][rest];
int res = dfs_memo(idx+1, rest); // 不裝
if (w[idx] <= rest) {
int take = v[idx] + dfs_memo(idx+1, rest - w[idx]);
if (take > res) res = take;
}
visited[idx][rest] = 1;
return memo[idx][rest] = res;
}複雜度：狀態數 n × C，每狀態 O(1) → O(nC) 時間、O(nC) 空間
int dp[MAX_N+1][MAX_C+1];
// dp[i][j] = 前 i 件物品、容量 j 的最大價值
for (int i=1; i<=n; i++) {
for (int j=0; j<=C; j++) {
dp[i][j] = dp[i-1][j]; // 不裝第 i 件
if (w[i-1] <= j) {
int take = v[i-1] + dp[i-1][j - w[i-1]];
if (take > dp[i][j]) dp[i][j] = take;
}
}
}
// 答案：dp[n][C]int dp[MAX_C+1] = {0};
// 關鍵：逆序遍歷容量，避免覆蓋上一輪數據
for (int i=0; i=w[i]; j--) { // 必須逆序！
int take = v[i] + dp[j - w[i]];
if (take > dp[j]) dp[j] = take;
}
}
// 答案：dp[C] 為什麼逆序？ dp[j] 依賴 dp[j-w[i]] (上一輪狀態)，正序會提前覆蓋導致「重複裝入」。
// 一維 DP 方案重構
int choice[MAX_N][MAX_C+1]; // 記錄第 i 件、容量 j 是否選擇
for (int i=0; i=w[i]; j--) {
int take = v[i] + dp[j - w[i]];
if (take > dp[j]) {
dp[j] = take;
choice[i][j] = 1;
}
}
}
// 回溯構造方案
int rest = C;
for (int i=n-1; i>=0; i--) {
if (choice[i][rest]) {
choose[i] = 1;
rest -= w[i];
} else {
choose[i] = 0;
}
} #include
#include
int main() {
int n, C;
if (scanf("%d %d", &n, &C) != 2) return 1;
if (n <= 0 || C <= 0) return 1;
int *w = malloc(n * sizeof(int));
int *v = malloc(n * sizeof(int));
for (int i=0; i=w[i]; j--) {
int take = v[i] + dp[j - w[i]];
if (take > dp[j]) {
dp[j] = take;
choice[i*(C+1) + j] = 1;
}
}
}
printf("%d\n", dp[C]);
// 可選：輸出方案
int rest = C;
for (int i=n-1; i>=0; i--) {
if (choice[i*(C+1) + rest]) {
printf("Item %d taken\n", i);
rest -= w[i];
}
}
free(w); free(v); free(dp); free(choice);
return 0;
} | 場景 | 推薦算法 | 複雜度 | 備註 |
|---|---|---|---|
| n ≤ 20, C 任意 | 遞歸回溯 + 剪枝 | O(2^n) | 實現簡單，適合小規模 |
| n ≤ 1000, C ≤ 10^5 | 一維 DP | O(nC) 時間, O(C) 空間 | 標準解法 |
| n ≤ 10^5, C ≤ 10^9 | 價值為狀態 DP / 貪心近似 | O(nV) 或 O(n log n) | 需根據數據特點選擇 |
| 需輸出方案 | 記錄 choice 回溯 | 額外 O(nC) 空間 | 或二維 DP 直接回溯 |
for(j=w[i]; j<=C; j++)for(j=C; j>=0; j--) for(k在組內) dp[j]=max(dp[j], dp[j-w[k]]+v[k])01 背包從遞歸回溯 O(2^n) → 備忘錄 O(nC) → 底向上 DP O(nC) → 一維 DP O(C) 空間，體現了「狀態定義 → 狀態轉移 → 實現優化」的動態規劃核心思想。一維逆序遍歷是空間優化的關鍵技巧，**必須理解依賴關係才能正確應用**。實際工程中根據 n、C、數據分佈選擇合適算法，並注意 long long 防溢出、動態分配防棧溢出。
