HDU 2844 Coins - 多重背包二進制優化

題目大意

n 種硬幣，面值 a[i]，數量 c[i]。求能湊出多少種 1~m 之間的金額（恰好湊出）。

多重背包優化策略

• 01 背包：for i=V..cost 逆序
• 完全背包：for i=cost..V 正序
• 多重背包：若 cost * cnt ≥ V 視為完全背包；否則二進制拆分 1,2,4,...,餘數 轉為多個 01 物品

代碼實現

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

int n, m, dp[100010], a[100010], c[1010];

void pack01(int cost, int w) {
    for (int i = m; i >= cost; i--) dp[i] = max(dp[i], dp[i-cost] + w);
}
void packAll(int cost, int w) {
    for (int i = cost; i <= m; i++) dp[i] = max(dp[i], dp[i-cost] + w);
}
void multiPack(int cost, int w, int cnt) {
    if (cost * cnt >= m) { packAll(cost, w); return; }
    int k = 1;
    while (k < cnt) { pack01(cost*k, w*k); cnt -= k; k <<= 1; }
    pack01(cost*cnt, w*cnt);
}

int main() {
    while (scanf("%d%d", &n, &m) == 2 && (n||m)) {
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        for (int i = 0; i < n; i++) scanf("%d", &c[i]);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++) multiPack(a[i], a[i], c[i]);
        int ans = 0;
        for (int i = 1; i <= m; i++) if (dp[i] == i) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

關鍵細節

1. 價值 = 面值，故 dp[i] == i 表示恰好湊出 i
2. 二進制拆分將 O(cnt) 優化為 O(log cnt)
3. 數組大小 100010 覆蓋 m ≤ 100000