POJ 1742 Coins：多重背包變種求可組合金額種類數

POJ 1742 Coins：多重背包變種求可組合金額種類數

問題描述

有 n 種硬幣，面值 A1..An，每種數量 C1..Cn。Tony 想付款 1..m 之間的任意整數金額（無找零），問有多少種金額能湊出？

約束：n ≤ 100，m ≤ 100000，Ai ≤ 100000，Ci ≤ 1000。

算法思路：優化的多重背包

標準多重背包二進制拆分會 TLE。本題使用 單調隊列優化 或 計數器法：

• dp[j]：金額 j 是否可湊出（布爾）
• sum[j]：湊出金額 j 時，當前硬幣已使用次數
• 對每種硬幣，sum 歸零，正序枚舉金額
  if (!dp[j] && dp[j-Ai] && sum[j-Ai] < Ci) { dp[j]=1; sum[j]=sum[j-Ai]+1; ans++; }

時間 O(n×m)，空間 O(m)，完美通過。

完整 AC 代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100007
int dp[N], sum[N];
int va[200], all, n, num[200];

int main() {
    int i;
    while (scanf("%d%d", &n, &all), n + all) {
        for (i = 0; i < n; i++) scanf("%d", &va[i]);
        for (i = 0; i < n; i++) scanf("%d", &num[i]);
        for (i = 0; i <= all; i++) dp[i] = 0;
        dp[0] = 1;
        int j, ans = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j <= all; j++) sum[j] = 0;
            for (j = va[i]; j <= all; j++)
                if (!dp[j] && dp[j - va[i]] && sum[j - va[i]] < num[i]) {
                    dp[j] = 1;
                    sum[j] = sum[j - va[i]] + 1;
                    ans++;
                }
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點解析

1. sum 數組記錄「當前硬幣在湊出該金額時的使用次數」
2. 正序枚舉保證同一硬幣可重複使用
3. sum[j] = 0 重置是關鍵：每種硬幣獨立計數
4. 只統計新湊出的金額（!dp[j]），避免重複計數