牛客网–采药（01背包）

输入描述: 输入的第一行有两个整数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.cn/100207.html原文链接：https://javaforall.cn