HDU - 2844 - coins

yxyxyxyxyx / 2023-09-05 / 原文

HDU - 2844 - coins (多重背包)

题意：

大壮想买东西，他有n种不同面值的硬币，每种有 $c_i$ 个，他不想找零，也不想买超过价值m的东西，问他有多少种支付方式。$n(1 ≤ n ≤ 100),m(m ≤ 100000)$

分析：

可以发现m的范围不大，直接在m中遍历。转化为给定一个容量为m的背包，问装入不同方案时，不同价值的数量。

显然是一个多重背包，需要使用二进制优化，标记出现过的不同价值即可。

为什么呢？因为求的是m中出现过的价值，那么如果一个价值可以被凑出来，假设为x，那么当背包容量刚好为x时，一定没有比它更优的方案。

const int N = 110;
const int M = 1e5 + 10;
void solve() {
    int n, m;
    while (cin >> n >> m && n != 0 && m != 0) {
        memset(dp, 0, sizeof dp);
        for (int i = 1; i <= n; i++)cin >> a[i];
        int pos = 0;
        for (int i = 1; i <= n; i++) {
            int x; cin >> x;
            int k = 1;
            while (k <= x) {
                if (pos > m)break;
                v[++pos] = a[i] * k;
                x -= k;
                k <<= 1;
            }
            if (x && pos < m) v[++pos] = a[i] * x;
        }
        for (int i = 1; i <= pos; i++) {
            for (int j = m; j >= v[i]; j--) {
                dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
                if (dp[j] > 0)vi[dp[j]]++;
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            if (vi[i])ans++;
        }
        cout << ans << endl;
        memset(vi, 0, sizeof vi);
    }
}

题目链接：Problem - 2844 (hdu.edu.cn)