HDU 2844 多重背包問題：二進制優化模板深度解析

問題描述

給定 n 種物品與背包容量 m，每種物品有價值 v[i] 與數量 c[i]。任取若干物品（不超過各自數量限制），使總價值不超過 m。求能組成的不同總價值個數（不含 0）。

核心思想：二進制優化

多重背包直接轉化為 01 背包會導致物品數量爆炸。二進制優化利用任意整數可拆分為若干 2 的冪次之和（如 13 = 1 + 4 + 8）的性質，將數量 c 拆分為 1, 2, 4, ..., 2ᵏ, c - (2ᵏ⁺¹ - 1) 組，每組視為一個 01 物品，時間複雜度從 O(n × m × c) 降為 O(n × m × log c)。

三種背包模板函數

void complete_pack(int v) {          // 完全背包（無限件）
    for (int i = v; i <= m; ++i)
        if (dp[i - v]) dp[i] = 1;
}

void onezero_pack(int v) {           // 01 背包（單件）
    for (int i = m; i >= v; --i)
        if (dp[i - v]) dp[i] = 1;
}

void multiple_pack(int v, int c) {   // 多重背包（c 件）
    if (v * c >= m) complete_pack(v);   // 數量足夠視為完全背包
    else {
        int k = 1;
        while (k < c) {
            onezero_pack(k * v);
            c -= k;
            k <<= 1;
        }
        onezero_pack(c * v);            // 處理剩餘部分
    }
}

狀態定義與轉移

• dp[i]：是否能組成價值 i（布林值）
• 初始 dp[0] = 1，其餘為 0
• 遍歷每種物品調用 multiple_pack(v[i], c[i])
• 最終統計 dp[1..m] 中為 1 的個數

完整 AC 代碼

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

int n, m;
int dp[100010];

void complete_pack(int v) {
    for (int i = v; i <= m; ++i)
        if (dp[i - v]) dp[i] = 1;
}

void onezero_pack(int v) {
    for (int i = m; i >= v; --i)
        if (dp[i - v]) dp[i] = 1;
}

void multiple_pack(int v, int c) {
    if (v * c >= m) complete_pack(v);
    else {
        int k = 1;
        while (k < c) {
            onezero_pack(k * v);
            c -= k;
            k <<= 1;
        }
        onezero_pack(c * v);
    }
}

int main() {
    int v[101], c[101];
    int i, ans;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n + m == 0) break;
        for (i = 1; i <= n; ++i) scanf("%d", &v[i]);
        for (i = 1; i <= n; ++i) scanf("%d", &c[i]);
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (i = 1; i <= n; ++i) multiple_pack(v[i], c[i]);
        ans = 0;
        for (i = 1; i <= m; ++i) if (dp[i]) ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

關鍵細節與易錯點

1. 數組大小：dp 開到 m+1（題目 m ≤ 100000），v, c 開 n+1（n ≤ 100）
2. 輸入結束條件：n + m == 0 而非單獨判斷 n
3. 二進制拆分邊界：while (k < c) 而非 k <= c，剩餘部分單獨處理
4. 完全背包判斷：v * c >= m 時直接按完全背包處理，避免不必要的拆分

複雜度分析

• 時間：O(n × m × log C_max)，其中 C_max 為最大數量
• 空間：O(m) 一維 DP 數組

此模板為多重背包「存在性」問題的標準解法，若需求最大價值或方案數，只需將 dp 改為 int 並調整轉移邏輯即可。熟練掌握三種背包函數的寫法與適用場景，是 ACM/ICPC 競技程式設計的基本功。