A44146. 最大价值
填空题
中等
知识点
题目描述
最大价值
题目描述
一名种菜的农民伯伯。需要在给定的时间内完成种菜，现有m种不同的蔬菜提供给农民伯伯选择，且每种蔬菜种植花费的时间不同，每种蔬菜成熟后售卖的价值也不同。
要求：
1.在限定的总时间内进行蔬菜种植，并且种植蔬菜的种类不能超出限制的数量；
2.选择最优的种植方案使得蔬菜成熟后售卖的总价值最大（可选择不同的蔬菜种植）。
例如：
给定的总时间限制为55，种植蔬菜的种类限制为3；
3种蔬菜，种菜的花费时间及售卖价格分别为：第一种21和9，第二种20和2，第三种30和21。
最优的种植方案是选择种植第一种和第三种，两种蔬菜种植总时间30+21，未超过总时间限制55。所种植蔬菜为两种，也未超过种类限制的3种。最大总价值为9+21=30，这个方案是最优的。
输入格式
第一行输入两个正整数t（1<=t<=600）和m（1<=m<=50），用一个空格隔开，t代表种菜总时间限制，m代表最多可种植蔬菜种类的限制；
接下来的m行每行输入两个正整数t1（1<t1<101）和p（1<p<101）且用一个空格隔开，t1表示每种蔬菜种植需要花费的时间，p表示对应蔬菜成熟后售卖的价值。
输出格式
输出一个正整数，表示选择最优的种植方案后，蔬菜成熟后售卖的最大总价值。
样例输入
53 3
21 9
20 2
30 21
样例输出
30
参考答案
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int t,m;
struct greens{
int tt,p;
}a[605];
int f[55][605];
int main()
{
cin>>t>>m;
for(int i=1;i<=m;i++)
cin>>a[i].tt>>a[i].p;
for(int i=1;i<=m;i++)
for(int j=1;j<=t;j++){
f[i][j]=f[i-1][j];
if(j>=a[i].tt)
f[i][j]=max(f[i][j],f[i-1][j-a[i].tt]+a[i].p);
}
cout<<f[m][t]<<endl;
return 0;
}
上一题
下一题