学校的面包的价格只有两种,1 元和 2 元,但面包还有一个美味值,某信息 学同学手拿 v 元钱,希望能买到的面包的美味值总和最大。输入数据第一行是两个正整数 n 和 v,n 表示面包的数量,v 表示同学手中的钱 数。 接下来 n 行,每行两个正整数,第一个正整数表示面包的价格(只有 1 和 2 两种 可能),另一个正整数表示这个面包的美味值输出能得到的最大美味值总和。c++代码
时间: 2024-02-13 21:01:40 浏览: 62
好的,以下是代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}
```
输入格式:
第一行为面包的数量 `n` 和手上的钱数 `m`。
接下来 `n` 行,每行两个正整数,第一个正整数表示面包的价格,第二个正整数表示这个面包的美味值。
输出格式:
输出能得到的最大美味值总和。
时间复杂度为 $O(nm)$。
相关问题
学校的面包的价格只有两种,1 元和 2 元,但面包还有一个美味值,某信息 学同学手拿 v 元钱,希望能买到的面包的美味值总和最大.输出能得到的最大美味值总和。c++代码
好的,以下是代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> v[i];
w[i] = v[i];
}
cin >> m;
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
```
输入格式:
第一行为面包的种类数 `n`。
接下来一行为每种面包的价格 `v[i]`。
最后一行为手上的钱数 `m`。
输出格式:
输出能得到的最大美味值总和。
时间复杂度为 $O(nm)$。
阅读全文