ACdream OJ 1110 多重背包：二進制優化與單調隊列兩種解法

題目大意

有 n 種物品，第 i 種價值 a[i]，數量 num[i]。背包容量 cap。求能湊出的不同總價值數量（0 不計）。多組測試數據。

解法一：二進制拆分轉 01 背包

將數量 k 拆分為 1, 2, 4, ..., 2^p, k - (2^p - 1)，每份視為一個 01 物品，價值乘以份數。總物品數 O(n log max_num)，隨後跑標準 01 背包（倒序遍歷容量）。

解法二：單調隊列優化 O(n·cap)

對每個物品，按模 a[i] 分組處理。對於餘數 r，考慮容量 j = r + m·a[i] 的 DP 值。維護單調隊列保持窗口大小 ≤ num[i]，實現 O(1) 轉移。代碼較長但理論最優。

解法三：簡單計數數組法（本題足夠）

利用 rem[j] 記錄達成容量 j 所用當前物品數量。正序遍歷容量（完全背包順序），若 rem[j] < num[i] 則可轉移。時間 O(n·cap)，代碼極短，本題數據範圍下極快。

核心代碼（計數數組法）

#include <bits/stdc++.h>
using namespace std;
const int MAXC = 100010;
bool dp[MAXC];
int rem[MAXC];
int a[103], num[103];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        int n, cap; cin >> n >> cap;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> num[i];
        fill(dp, dp + cap + 1, false);
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            fill(rem, rem + cap + 1, 0);
            for (int j = 0; j <= cap; j++) {
                if (j + a[i] > cap || rem[j] >= num[i]) continue;
                if (dp[j]) {
                    if (!dp[j + a[i]]) {
                        dp[j + a[i]] = true;
                        rem[j + a[i]] = rem[j] + 1;
                    } else {
                        rem[j + a[i]] = min(rem[j + a[i]], rem[j] + 1);
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= cap; i++) if (dp[i]) ans++;
        cout << "Case " << tc << ": " << ans << "\n";
    }
    return 0;
}

關鍵點解析

• rem[j] 記錄「湊出 j 所用第 i 種物品的個數」。
• 正序遍歷 j 保證同一物品可重複使用（完全背包順序）。
• rem[j] >= num[i] 直接跳過，實現數量限制。
• 若目標狀態已為 true，取 min 保留較小用量，利於後續擴展。

複雜度

總結

多重背包核心在於「數量限制」的高效處理。計數數組法 代碼最短、思路最直觀，適用於 n·cap ≤ 10⁷ 量級；二進制拆分 通用性強，適合物品數量大但種類少；單調隊列 是理論極致，競賽模板必備。根據題目數據範圍靈活選擇。