首页 > 代码库 > [POJ 1742] Coins 【DP】
[POJ 1742] Coins 【DP】
题目链接：POJ - 1742
题目大意
现有 n 种不同的硬币，每种的面值为 Vi ，数量为 Ni ，问使用这些硬币共能凑出 [1,m] 范围内的多少种面值。
题目分析
使用一种 O(nm) 的 DP （据说这是类多重背包？），枚举每一种硬币，对于每一种硬币 i 枚举每一个面值 j ，如果这个面值 j 使用前 i-1 种硬币已经可以凑出，就直接跳过，否则尝试加入一个硬币 i ，看是否能凑出 j 。需要满足 (f[j - Vi] == true) && (UseNum[j - Vi] + 1 <= Ni) ，这样就可以了。对于每一个 i ，枚举 j 之前将 UseNum 数组清零。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 100 + 5, MaxM = 100000 + 5;int n, m, Ans;int V[MaxN], Num[MaxN], UseNum[MaxM];bool f[MaxM];int main(){ while (true) { scanf("%d%d", &n, &m); if (n == 0 && m == 0) break; for (int i = 1; i <= n; ++i) scanf("%d", &V[i]); for (int i = 1; i <= n; ++i) scanf("%d", &Num[i]); Ans = 0; for (int i = 1; i <= m; ++i) f[i] = false; f[0] = true; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) UseNum[j] = 0; for (int j = V[i]; j <= m; ++j) { if (f[j]) continue; if (f[j - V[i]] && UseNum[j - V[i]] + 1 <= Num[i]) { f[j] = true; UseNum[j] = UseNum[j - V[i]] + 1; } } } for (int i = 1; i <= m; ++i) if (f[i]) ++Ans; printf("%d\n", Ans); } return 0;}
[POJ 1742] Coins 【DP】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。