群晖做网站,东莞网络推广系统,马鞍山建设工程监督站建管处网站,深圳设计研究院总院题目链接#xff1a;POJ - 1742 题目大意 现有 n 种不同的硬币#xff0c;每种的面值为 Vi #xff0c;数量为 Ni #xff0c;问使用这些硬币共能凑出 [1,m] 范围内的多少种面值。 题目分析 使用一种 O(nm) 的 DP #xff08;据说这是类多重背包#xff1f;#xff09;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 algorithmusing 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;
}转载于:https://www.cnblogs.com/JoeFan/p/4165769.html
