POJ 1742 Coins 多重背包優化DP（重複條目）

問題描述

同 ID 3481。Silverland 硬幣系統，n 種面值 A_i，各 C_i 枚。求 1..m 中能湊出的金額數。多測試用例，0 0 結束。

優化 DP 狀態

dp[j] = 用前 i 種硬幣湊成 j 時，第 i 種硬幣剩餘最大可用數（-1 表示不可達）。
轉移：
- 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

完整代碼

#include 
#include 
#include 
using namespace std;

int dp[100005], A[105], C[105];

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

複雜度與優勢

• 時間 O(nm) = 10⁷，空間 O(m) = 10⁵
• 無需二進制拆分，無需單調隊列，代碼極短
• 適用於「可行性」類多重背包（而非最大價值）

注意

輸入格式：第二行包含 2n 個整數，先 n 個 A_i，後 n 個 C_i。讀入時需分兩次循環或一次讀 2n 個。