输入描述:
输入的第一行有两个整数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;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/100207.html原文链接：https://javaforall.net
