A37146. 买瓜子校庆，采购瓜子。资金N(1<=N<=1000)元，M(1<=M<=30)种瓜子。问最多能采购多少千克的瓜子？比如N=80元，M=2种。第1种，每袋18元10千克；第2种，每袋30元20千克。输入样例80 218 1030 20输出样例50提示：18+30+30=78元 10+20+20=50千克
填空题
困难
知识点
题目描述
买瓜子
校庆，采购瓜子。资金N(1<=N<=1000)元，M(1<=M<=30)种瓜子。问最多能采购多少千克的瓜子？比如N=80元，M=2种。第1种，每袋18元10千克；第2种，每袋30元20千克。
输入样例
80 2
18 10
30 20
输出样例
50
提示：18+30+30=78元 10+20+20=50千克
参考答案
#include<bits/stdc++.h>
using namespace std;
int dp[50][1010]; //表示，前i个物品，在价值w的情况下，最大的重量是dp[i][w]
int wt[1010],v[50]; //wt是价格，v是重量
int n,w;
int main()
{
cin>>w>>n;
for(int i=1;i<=n;i++)
cin>>wt[i]>>v[i]; //wt[i]代表第i种瓜子多少钱 v[i]代表第i种瓜子多少千克
for(int i=1;i<=n;i++) //遍历n种瓜子，每种要么选，要么不选
{
for(int j=1;j<=w;j++) //j是价格
{
if(j>=wt[i]) //wt是价格
{
if(dp[i-1][j]>dp[i][j-wt[i]]+v[i])
{
dp[i][j]=dp[i-1][j];
}
else
{
dp[i][j]=dp[i][j-wt[i]]+v[i];
}
}
else
{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<dp[n][w]<<endl;
return 0;
}
上一题
下一题