HDOJ 2191 多重背包模板題：二進制拆分優化完整實現

問題描述

標準多重背包問題：給定 n 容量、m 種物品，每種有價值 p[i]、重量 h[i]、數量 c[i]，求最大價值。

代碼實現

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

int n, m, dp[102];

void zero_one(int weight, int value) {
    for (int j = n; j >= weight; j--)
        dp[j] = max(dp[j], dp[j - weight] + value);
}

int main() {
    int t, p[102], h[102], c[102];
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < m; i++)
            scanf("%d %d %d", &p[i], &h[i], &c[i]);
        
        memset(dp, 0, sizeof(dp));
        
        for (int i = 0; i < m; i++) {
            if (p[i] * c[i] > n) {  // 完全背包優化
                for (int j = p[i]; j <= n; j++)
                    dp[j] = max(dp[j], dp[j - p[i]] + h[i]);
            } else {  // 二進制拆分
                int k = 1;
                while (k < c[i]) {
                    zero_one(k * p[i], k * h[i]);
                    c[i] -= k;
                    k *= 2;
                }
                zero_one(c[i] * p[i], c[i] * h[i]);
            }
        }
        printf("%d\n", dp[n]);
    }
    return 0;
}

核心優化點

1. 完全背包判斷：p[i] * c[i] > n 時，該物品數量足夠視為無限，用正序循環
2. 二進制拆分：將數量 c[i] 拆為 1, 2, 4, ..., remainder，轉為若干 01 物品
3. 01 背包逆序：zero_one 內部用逆序循環保證每物品只用一次
4. 狀態定義：dp[j] 表示容量 j 時的最大價值

複雜度分析

• 時間：O(m × n × log C) - 拆分後物品數按對數級增長
• 空間：O(n) - 一維滾動數組

模板適用性

此代碼為標準多重背包模板，適用於 HDOJ 2191 及同類問題（如 POJ 1014、POJ 1742 等），只需根據題目調整數組大小與輸入格式。