算法學習筆記：0/1 背包問題動態規劃詳解與物品追蹤

問題描述

有 M 件物品，體積 W[i]，價值 P[i]。背包容量 V。每件至多取一次，求最大總價值。並輸出選取的物品編號。

DP 狀態與轉移

• dp[j]：容量為 j 時的最大價值。
• 遍歷物品 i = 1..M，容量 j = V..W[i] **逆序** 更新：
  dp[j] = max(dp[j], dp[j - W[i]] + P[i])。
• 逆序保證每件物品在當前輪次最多被使用一次（避免重複選取）。

C++ 核心代碼

int dp[V+1] = {0};
for (int i = 0; i < M; ++i) {
    for (int j = V; j >= W[i]; --j) {
        if (dp[j] < dp[j - W[i]] + P[i])
            dp[j] = dp[j - W[i]] + P[i];
    }
}
cout << dp[V] << endl;

追蹤選取物品

1. 保存 W[i], P[i] 數組。
2. 找到實際使用容量 used = V；而 dp[used] == dp[used-1] 則 used--（背包未必裝滿）。
3. 逆序遍歷物品 i = M-1..0：若 used >= W[i] && dp[used] == dp[used - W[i]] + P[i]，則選取了物品 i，used -= W[i]。

完整追蹤代碼

int used = V;
while (used > 0 && dp[used] == dp[used-1]) --used;
for (int i = M-1; i >= 0; --i) {
    if (used >= W[i] && dp[used] == dp[used - W[i]] + P[i]) {
        cout << i+1 << " "; // 物品編號
        used -= W[i];
    }
}

關鍵點總結

• 逆序遍歷容量是 0/1 背包去重的核心。
• 追蹤時從最後狀態反推，利用最優子結構性質。
• 空間優化至一維數組，時間 O(MV)。