POJ 1742 硬幣問題：多重背包優化與狀態可達性統計

問題描述

農夫 John 想買價值 T 美分的物品，有 N 種硬幣（面值 Vᵢ，數量 Cᵢ）。店主擁有無限硬幣並能最優找零。John 想**最小化雙方硬幣總數**（付出 + 找零）。輸出最小硬幣數，不可能輸出 -1。
N ≤ 100, T ≤ 10,000, Vᵢ ≤ 120, Cᵢ ≤ 10,000。

核心轉化

John 支付金額 S（S ≥ T），店主找零 S-T。雙方硬幣數之和 = `f₁(S) + f₂(S-T)`，其中：
- `f₁(x)`：John 用有限硬幣湊 x 的最小硬幣數（多重背包）。
- `f₂(x)`：店主用無限硬幣湊 x 的最小硬幣數（完全背包）。

預計算 `f₂`（完全背包），再枚舉 John 可能支付的金額 S（從 T 到 T+maxV），取最小值。

多重背包優化：二進制拆分

將數量 Cᵢ 拆分為 1, 2, 4, ..., 2ᵏ, 餘數，轉化為若干 01 背包物品，再用 01 背包 DP。或用**單調隊列優化**（O(N·T)），但二進制拆分代碼更短、常數可接受。

更簡潔做法：可達性統計（題目實際只問能湊出多少種金額）

原文輸出樣例與代碼顯示：實際只需統計 John 能湊出的**不同金額數量**（而非最小化硬幣數）。這可能是題目理解差異，但提供的代碼均為「可達性 DP」。

可達性 DP 代碼（二進制拆分版）

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

const int MAXT = 100001;
bool dp[MAXT];
int V[101], C[101];

int main() {
    int N, T;
    while (scanf("%d%d", &N, &T) == 2 && (N || T)) {
        for (int i = 1; i <= N; i++) scanf("%d", &V[i]);
        for (int i = 1; i <= N; i++) scanf("%d", &C[i]);

        memset(dp, 0, sizeof(dp));
        dp[0] = true;

        for (int i = 1; i <= N; i++) {
            int v = V[i], c = C[i];
            if (v * c >= T) {  // 退化為完全背包
                for (int j = v; j <= T; j++)
                    if (!dp[j] && dp[j-v]) dp[j] = true;
            } else {
                int k = 1;
                while (k < c) {
                    int item = k * v;
                    for (int j = T; j >= item; j--)
                        if (!dp[j] && dp[j-item]) dp[j] = true;
                    c -= k; k <<= 1;
                }
                if (c > 0) {
                    int item = c * v;
                    for (int j = T; j >= item; j--)
                        if (!dp[j] && dp[j-item]) dp[j] = true;
                }
            }
        }

        int ans = 0;
        for (int j = 1; j <= T; j++) if (dp[j]) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

更優雅的完全背包轉化（大神寫法）

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

const int MAX = 100010;
int dp[MAX], use[MAX];
int a[MAX], b[MAX];

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

此法用 `use[j]` 記錄湊出 j 所用第 i 種硬幣的數量，**將多重背包直接在完全背包框架下 O(N·T) 解決**，無需拆分，極其優雅高效。

關鍵點總結

總結

POJ 1742 展示了多重背包的三種經典優化。**`use[]` 狀態記錄法**將「限制物品使用次數」融入完全背包循環，是競賽中極具性價比的模板。理解其原理：`dp[j]` 只從 `dp[j-v]` 轉移而來，且 `use[j] = use[j-v] + 1` 保證不超限，極其巧妙。