A25995. 最大值
题目描述
最大值
题目描述
某校庆祝元旦需要采购一些瓜子在联欢会上食用，学校给了固定资金 n 元让小蓝去超市采购瓜子，且要求采购最多的瓜子。到了超市发现有 m 种瓜子，且都是成袋售卖。小蓝这下为难了，不知道如何才能用固定资金采购最多的瓜子。在给出每种瓜子每袋的价格、每袋的重量，请你帮助小蓝计算下用 n 元最多能采购多少瓜子。
例如：
给定的资金 n 为 80 元，瓜子种类 m 为 2 种：
第一种瓜子每袋 18 元，每袋 10 千克；
第二种瓜子每袋 30 元，每袋 20 千克；
用 80 元资金最多可以买 50 千克瓜子（买 2 袋第二种，1 袋第一种的，总重量 50 千克，使用资金 78 元）。
输入描述：
第一行输入两个正整数 n（1 ≤n ≤1000）和 m（1 ≤m ≤ 30），用一个空格隔开，n 代表买瓜子的资金，m 代表超市瓜子种类数。
接下来输入 m 行，每行输入两个正整数 p（1 < p < 101）和 k（1 < k < 101）且用一个空格隔开，p 代表每袋瓜子的价格，k 代表每袋瓜子的重量。
输出描述：
输出一个正整数，代表 n 元钱最多能采购到的瓜子重量（千克）。
样例输入：
80 2
18 10
30 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;
}答案解析
// 参考代码2
#include <bits/stdc++.h>
using namespace std;
int n, m, p[35], k[35];
int f[1005];
int Max(int a, int b) {
if (a > b)
return a;
return b;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", p + i, k + i);
for (int j = p[i]; j <= n; j++) {
f[j] = Max(f[j], f[j - p[i]] + k[i]);
}
}
printf("%d\n", f[n]);
return 0;
}