GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A41780. $硬币问题有N（不大于100）种硬币，编号为1至N，已知每种硬币的重量（不超过100的正整数）和面额（不超过100的正整数），每种硬币数量不限。选取总重量不超过C（不大于1000的正整数）的硬币，最多能获得多少总面额？输入第一行输入N 第二行输入C 第三行输入各硬币重量，用空格隔开第四行输入各硬币价值，用空格隔开输出最大总面额样例输入351 2 51 3 6样例输出7$

填空题困难

知识点

完全背包动态规划一维数组优化

题目描述

硬币问题 有N（不大于100）种硬币，编号为1至N，已知每种硬币的重量（不超过100的正整数）和面额（不超过100的正整数），每种硬币数量不限。选取总重量不超过C（不大于1000的正整数）的硬币，最多能获得多少总面额？ 输入 第一行输入N 第二行输入C 第三行输入各硬币重量，用空格隔开 第四行输入各硬币价值，用空格隔开 输出 最大总面额 样例输入 35 1 2 5 1 3 6 样例输出 7

参考答案

#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;
}

上一题下一题