POJ 1742 Coins 多重背包優化DP

問題描述

n 種硬幣（n ≤ 100），第 i 種面值 A_i，數量 C_i。查詢 1 到 m（m ≤ 10⁵）中有多少金額能湊出。多組測試，0 0 結束。

優化 DP 狀態定義

dp[j] = 用前 i 種硬幣湊成金額 j 時，第 i 種硬幣剩餘的最大可用數量（-1 表示不可湊出）。
初始 dp[0] = 0，其餘 -1。
對第 i 種硬幣：
若 dp[j] >= 0 → dp[j] = C[i]（不需要用第 i 種）
否若 j < A[i] 或 dp[j-A[i]] <= 0 → dp[j] = -1
否 → dp[j] = dp[j-A[i]] - 1（用一枚第 i 種）

代碼實現

int dp[100005];
int main() {
    while (scanf("%d%d", &n, &m), n||m) {
        fill(dp, dp+m+1, -1);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int a, c; scanf("%d%d", &a, &c);
            for (int j = 0; j <= m; ++j) {
                if (dp[j] >= 0) dp[j] = c;
                else if (j < a || dp[j-a] <= 0) dp[j] = -1;
                else dp[j] = dp[j-a] - 1;
            }
        }
        int ans = 0;
        for (int j = 1; j <= m; ++j) if (dp[j] >= 0) ++ans;
        printf("%d\n", ans);
    }
}

原理分析

這是「單調隊列優化」的簡化版。dp[j] 記錄剩餘數量，實際上是在檢查 j 能否由 j-A[i] 轉移而來且還有硬幣可用。時間 O(nm) = 10⁷，空間 O(m)，極快。

對比傳統多重背包

• 二進制拆分：物品數變多，總複雜度 O(m∑logC_i)
• 單調隊列：O(nm)，代碼較複雜
• 本方法：O(nm)，代碼極短，通用性強