POJ 1742 Coins 多重背包優化解法：O(NM) 狀態壓縮與二進制拆分對比

問題描述

給定 n 種面值的硬幣，每種硬幣有限數量 C[i]，求能組成的不超過 m 的金額種數。

解法一：優化的多重背包 O(NM) - 狀態壓縮 + used 數組

核心思想：用 f[j] 表示金額 j 是否可組成（0/1），用 used[j] 記錄組成金額 j 時當前硬幣已用數量。

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

int main() {
    int n, m, A[102], C[102];
    int f[100002], used[100002];
    
    while (scanf("%d %d", &n, &m), 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(f, 0, sizeof(f));
        f[0] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) used[j] = 0;  // 重置使用計數
            
            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;
}

關鍵點解析

• 正序循環：j = A[i] 到 m，因為同一硬幣可重複使用
• used 數組：精確控制每種硬幣使用次數不超過 C[i]
• 狀態轉移：只有當 f[j]==0 且 f[j-A[i]]==1 且未超限時才更新
• 時間複雜度：O(n × m)，POJ 測試數據下可通過

解法二：經典二進制拆分轉 01 背包

將數量 C[i] 拆分為 1, 2, 4, ..., 2^k, remainder，每組視為一個 01 物品。

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

int main() {
    // ... 讀入數據 ...
    for (int i = 0; i < n; i++) {
        int sum = A[i] * C[i];
        if (sum > m) {  // 退化為完全背包
            for (int j = A[i]; j <= m; j++)
                dp[j] = max(dp[j], dp[j - A[i]] + A[i]);
        } else {
            int k = 1;
            while (k < C[i]) {
                zero_one(k * A[i], k * A[i]);
                C[i] -= k;
                k *= 2;
            }
            zero_one(C[i] * A[i], C[i] * A[i]);
        }
    }
    // 統計 dp[i] == i 的個數
}

兩種解法對比

核心心得

對於「求可組成金額種數」這類可行性問題，used 數組法更優；若涉及價值最大化，二進制拆分轉 01/完全背包更通用。