Coins HDU - 2844（多重背包 模板题）

http://acm.hdu.edu.cn/showproblem.php?pid=5572

题目大意

有n种面值的硬币，每种硬币有c[i]个，问1~m之间的所有价值，能用这些硬币组合出来的个数是多少个。(1≤n≤100), (m≤100000)

分析

明显的多重背包。把每种硬币二进制拆分优化。
详细看 背包问题整理

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[110], c[110]; // a[i]硬币面值 c[i]硬币个数
int v[1100], tot; // 重新分组后的tot个物品价值
bool f[N];
int main() {
int n, m;
while (cin >> n >> m, n) {
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> c[i];
tot = 0;
/*对每种面值的硬币二进制拆分 重新分组*/
for (int i = 1; i <= n; ++i) {
int x = 1;
while (c[i] >= x) {
v[++tot] = a[i] * x;
c[i] -= x;
x <<= 1;
}
if (c[i] > 0) v[++tot] = a[i] * c[i];
}
memset(f, false, sizeof(f));
f[0] = true; /*初始化 用任何硬币表示价值为0都为真*/
/*对二进制拆分后的tot个物品01背包*/
for (int i = 1; i <= tot; ++i) {
for (int j = m; j >= v[i]; --j) {
f[j] |= f[j - v[i]];
}
}
int ans = 0;
for (int i = 1; i <= m; ++i) {
ans += f[i];
}
cout << ans << endl;
}
return 0;
}

最后

以上就是稳重狗为你收集整理的Coins HDU - 2844（多重背包 模板题）的全部内容，希望文章能够帮你解决Coins HDU - 2844（多重背包 模板题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。