NYOJ 654：0/1 背包常數優化技巧——動態縮小內層循環範圍

背景

標準 0/1 背包內層循環為 for (v = V; v >= w[i]; --v)。當背包容量 V 很大（如 10⁶），但物品總體積遠小於 V 時，大量循環是無效的。NYOJ 654 正是利用此優化通過大數據測試。

優化原理

考慮第 i 個物品（倒序處理時），後續物品 i..n 的總體積為 sum_w = Σ_{k=i}^n w[k]。若當前容量 v > V - sum_w，則剩餘容量不足以裝下所有後續物品，但這不影響當前決策。實際上，只有 v ≥ w[i] 且 v ≤ V 才需更新。更精確地，對於第 i 輪，v 的有效下界是 max(w[i], V - sum_{k=i}^n w[k])。因為若 ，即使裝滿所有後續物品也超不了總容量 V，但這裡的邏輯是：我們只關心最終 dp[V]，倒推回來，第 i 輪只需更新到足以影響最終結果的範圍。

優化後循環結構

for (int i = 0; i < n; ++i) {
    int sum = 0;
    for (int j = i; j < n; ++j) sum += w[j]; // 計算 sum_{k=i}^n w[k]
    int bound = max(V - sum, w[i]); // 動態下界
    for (int v = V; v >= bound; --v) {
        dp[v] = max(dp[v], dp[v - w[i]] + val[i]);
    }
}

完整代碼 (NYOJ 654)

const int COST = 1e6 + 10;
const int M = 1e4 + 10;
int dp[COST];
int value[M];
int volume[M];

int main() {
    int Ncase;
    scanf("%d", &Ncase);
    while (Ncase--) {
        memset(dp, 0, sizeof(dp));
        int max_cost, n_bags;
        scanf("%d%d", &n_bags, &max_cost);
        for (int i = 0; i < n_bags; ++i) {
            scanf("%d%d", &volume[i], &value[i]);
        }
        for (int i = 0; i < n_bags; ++i) {
            int sum = 0;
            for (int j = i; j < n_bags; ++j) sum += volume[j];
            int bound = max(max_cost - sum, volume[i]);
            for (int j = max_cost; j >= bound; --j) {
                if (dp[j] < dp[j - volume[i]] + value[i]) {
                    dp[j] = dp[j - volume[i]] + value[i];
                }
            }
        }
        printf("Max experience: %d\n", dp[max_cost]);
    }
    return 0;
}

效果分析

• 時間節省：若 V = 10^6，但物品總體積僅 10⁴，內層循環次數從 ~10⁶ 降至 ~10⁴，加速 100 倍。
• 適用場景：背包容量遠大於物品總體積之和，或物品體積較大但數量少。
• 代價：每輪需 O(n) 計算後綴和，總額外 O(n^2)。若 n ≤ 10^4 可接受；若 n 更大，可預處理後綴和陣列降至 O(n)。

進一步優化：預處理後綴和

vector suffix_sum(n + 1, 0);
for (int i = n - 1; i >= 0; --i) suffix_sum[i] = suffix_sum[i + 1] + volume[i];
// 循環中直接用 bound = max(V - suffix_sum[i], volume[i]);

總結

這是一個「以空間換時間」的經典常數優化：利用問題結構（只需最終 dp[V]）動態縮小循環範圍。實戰中，配合後綴和預處理，能顯著降低大容量背包的運行時間，是 ACM/ICPC 選手必備技巧之一。