HDU2844 Coins（多重背包）

题目链接：HDU2844

题目描述：有 n n n 种硬币，每种硬币的面值为 a i a_i ai​，数量为 c i c_i ci​，现在要你求出能凑出总面值为 m m m 的方案数。

题目解析：多重背包，定义

dp[i]

为面值为 i i i 的状态是否可达。则状态转移方程为

dp[i] = dp[i] | dp[i - a[i]] | ... | dp[i - a[i] * c[i]]

。数量进行二进制优化。然后转化为01背包解决。

参考代码：

#include <iostream>
#include <cstring>
using namespace std;
int a[110], c[110], w[1010], dp[100010];
int main() {
    int n, m;
    while (cin >> n >> m && n && m) {
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> c[i];
        
        int cnt = 0, tmp;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; c[i] > 0; j *= 2) {
                tmp = min(j, c[i]);
                c[i] -= j;
                w[cnt++] = a[i] *tmp;
            }
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 0; i < cnt; i++) {
            for (int j = m; j >= w[i]; j--) {
                if (dp[j - w[i]]) dp[j] = 1;
            }
        }
        
        int ans = 0;
        for (int i = 1; i <= m; i++) ans += dp[i];
        cout << ans << endl;
    }
    return 0;
}