输入描述:
输入的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),T代表总共能够用来采药的时间,M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间(包括1和100)的的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出描述:
可能有多组测试数据,对于每组数据,
输出只包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
//01背包
#include<bits/stdc++.h>
using namespace std;
struct hert{
int time;
int value;
}hert[101];
int dp[1001];//T时间所得价值
int max(int i,int j){ return (i>j)?i:j;}
int main(){
int m,t;
int time[100];
int price[100];
while(cin>>t>>m){
for(int i=1;i<=m;i++){
cin>>hert[i].time>>hert[i].value;
}
for(int i=1;i<=t;i++){
dp[i]=0;
}
for(int i=1;i<=m;i++){//药草种类
for(int j=t;j>=hert[i].time;j–){//时间(限制因素)
dp[j]=max(dp[j],dp[j-hert[i].time]+hert[i].value);
}
}
cout<<dp[t]<<endl;
}
return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/100207.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...