HDU 2844 Coins 多重背包問題 - 二進制優化與完全背包轉換詳解

HDU 2844 Coins 多重背包問題 - 二進制優化與完全背包轉換詳解

題目描述

有 n 種硬幣，第 i 種面值為 val[i]，數量為 num[i]。給定 m，問區間 [1, m] 中有多少個整數可以由這些硬幣組合湊出（每種硬幣使用數量不超過擁有數量）。

核心算法：多重背包的二進制拆分優化

對於第 i 種硬幣：

• 若 val[i] * num[i] >= m：視為完全背包處理（數量足夠大，等價於無限供應）
• 否則：將 num[i] 拆分為 1, 2, 4, ..., 2^(k-1), num[i] - 2^k + 1 共 k+1 組，每組作為一個 01 背包 物品處理

這種拆分保證任意 0 到 num[i] 的選擇都能唯一表示，將多重背包轉化為 01 背包問題，時間複雜度從 O(n * m * max_num) 降為 O(n * m * log max_num)。

動態規劃狀態定義

dp[j] 表示湊出面值 j 的方法數（或可達性標記）。初始 dp[0] = 1，其餘為 0。

三種背包轉移模板

// 01 背包：倒序遍歷
void ZERO_ONE_PACK(int cost) {
    for (int i = m; i >= cost; i--)
        dp[i] += dp[i - cost];
}

// 完全背包：正序遍歷
void COMPLETE_PACK(int cost) {
    for (int i = cost; i <= m; i++)
        dp[i] += dp[i - cost];
}

// 多重背包：二進制拆分
void MULTIPLE_PACK(int cost, int num) {
    if (cost * num >= m) {  // 數量足夠，退化為完全背包
        COMPLETE_PACK(cost);
        return;
    }
    int k = 1;
    while (k < num) {
        ZERO_ONE_PACK(k * cost);
        num -= k;
        k <<= 1;
    }
    ZERO_ONE_PACK(num * cost);  // 處理剩餘部分
}

完整 AC 代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXM = 100000 + 5;
int dp[MAXM];
int cost[105], num[105];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++) scanf("%d", &cost[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
        
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            if (cost[i] * num[i] >= m) 
                COMPLETE_PACK(cost[i]);
            else 
                MULTIPLE_PACK(cost[i], num[i]);
        }
        
        int ans = 0;
        for (int i = 1; i <= m; i++)
            if (dp[i] > 0) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點總結

1. 二進制拆分：將數量 num 拆為 1, 2, 4, ..., 2^k, 余數，任意選擇數可唯一表示
2. 完全背包優化：當總面值超過 m 時直接按完全背包處理，避免不必要的拆分
3. 狀態壓縮：使用一維 dp 數組，01 背包倒序、完全背包正序
4. 統計答案：最終遍歷 dp[1..m]，計算非零狀態個數