简答题
偏难
#7201
硬币问题 有N(不大于100)种硬币,编号为1至N,已知每种硬币的重量(不超过100的正整数)和面额(不超过100的正整数),每种硬币数量不限。选取总重量不超过…
硬币问题
有N(不大于100)种硬币,编号为1至N,已知每种硬币的重量(不超过100的正整数)和面额(不超过100的正整数),每种硬币数量不限。选取总重量不超过C(不大于1000的正整数)的硬币,最多能获得多少总面额?
时间限制:1000
内存限制:65536
输入
第一行输入N 第二行输入C 第三行输入各硬币重量,用空格隔开 第四行输入各硬币价值,用空格隔开
输出
最大总面额
样例输入
3 5 1 2 5 1 3 6
样例输出
7
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int t[105], v[105];
int dp[1005];
int main() {
int n, c;
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> t[i];
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++) {
for (int j = t[i]; j <= c; j++) {
dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
}
}
cout << dp[c];
return 0;
}</pre>
这道题暂未补解析。