POJ 1742 多重背包可行性問題 (硬幣組合面值計數)

問題大意

有 n 種硬幣，面值 A[i]，數量 C[i]。查詢 1~m 中有多少面值能被這些硬幣精確湊出（不找零）。n ≤ 100, m ≤ 100000, 多組測試，0 0 結束。

核心思路：優化的多重背包 DP

定義 dp[j] 表示面值 j 是否可湊出 (0/1)。引入輔助數組 sum[j] 表示湊出面值 j 時當前硬幣已使用的數量。轉移：

for i = 0..n-1:
    fill(sum, sum + m + 1, 0)
    for j = w[i] to m:
        if (!dp[j] && dp[j - w[i]] && sum[j - w[i]] < c[i]) {
            dp[j] = 1;
            sum[j] = sum[j - w[i]] + 1;
        }

時間複雜度 O(n·m)，空間 O(m)。

完整代碼 (C++)

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

const int MAXM = 100005;
int dp[MAXM], sum[MAXM], w[105], c[105];

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

樣例解析

輸入：3 10
1 2 4 2 1 1 → 面值 1,2,4，數量 2,1,1。可湊出 1,2,3,4,5,6,7,8 共 8 種，輸出 8。