POJ 1742 Coins 多重背包問題：O(N·M) 優化解法詳解

題目大意

給定 n 種面值的硬幣，第 i 種面值為 A[i]，數量為 C[i]。求能組合出的不同金額總數（金額 ≤ m）。
資料範圍：n ≤ 100, m ≤ 100,000, A[i]·C[i] ≤ m。

核心難點

傳統多重背包二進制拆分或單調隊列優化在 POJ 上會 TLE。需採用 O(N·M) 狀態壓縮 DP，利用 used[j] 記錄「湊出金額 j 時，當前硬幣 i 已使用次數」。

演算法邏輯

• f[j] = 1 表示金額 j 可湊出。
• 對每種硬幣 i，初始化 used[0..m] = 0。
• 對 j = A[i] .. m 遞增掃描：
  若 f[j] == 0 且 f[j-A[i]] == 1 且 used[j-A[i]] < C[i]，
  則 f[j] = 1, used[j] = used[j-A[i]] + 1。
  （遞增掃描保證同一硬幣可重複使用，used 限制次數）

完整 C 代碼（POJ AC 版）

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

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && (n || m)) {
        int A[102], C[102];
        for (int i = 0; i < n; i++) scanf("%d", &A[i]);
        for (int i = 0; i < n; i++) scanf("%d", &C[i]);

        static int f[100002];      // 靜態陣列避免棧溢位
        static int used[100002];
        memset(f, 0, sizeof(f));
        f[0] = 1;

        for (int i = 0; i < n; i++) {
            memset(used, 0, sizeof(used)); // 每種硬幣重置 used
            for (int j = A[i]; j <= m; j++) {
                if (!f[j] && f[j - A[i]] && used[j - A[i]] < C[i]) {
                    f[j] = 1;
                    used[j] = used[j - A[i]] + 1;
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= m; i++) if (f[i]) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點解析

為何二進制拆分會 TLE？

二進制拆分將物品數擴增為 O(log C[i])，再跑 0/1 背包（逆序掃描），實際操作數約 Σ log C[i] · m。當 C[i] 較大且 m=100,000 時，常數因子過大導致超時。本題專用的 used[] 方法實際操作數僅 n·m = 10^7 量級，極易通過。

複雜度總結

• 時間：O(n · m) ≈ 10⁷ 操作，極快。
• 空間：O(m) 兩個 int 陣列 ≈ 800 KB。

延伸：HDU 1114 / ZOJ 1638 同類題型

此解法同樣適用於「求可組合金額種類數」的多重背包變體，是 OJ 多重背包經典模板之一。