采药 （C++代码）

解题思路:0/1背包问题，动态规划解决

注意事项:

参考代码:

#include<iostream>

#include<string.h>

using namespace std;

#define maxn 1001

#define MAX(a,b) a>b?a:b

int profit[maxn][maxn];

int Knapsack(int *time,int *value,int T,int M)

//profit[i][j]表示前i个物品装到容量为j的背包中的最大收益 

{

for(int i=0;i <= M;i++)profit[0][i]=0;

for(int i=0;i <= M;i++)profit[i][0]=0;

for(int i=1;i <= M;i++)

{

for(int j=1;j <=T;j++)

{

if(j<time[i])

{

profit[i][j]=profit[i-1][j];

}

else

{

profit[i][j]=MAX(profit[i-1][j],profit[i-1][j-time[i]]+value[i]);

}

}

}

return profit[M][T];

}

int main() 

{

int T,M;

cin>>T>>M;

int *time = new int[M+1];

int *value = new int[M+1];

for(int i=1;i <= M;i++)cin>>time[i]>>value[i];

cout<<Knapsack(time,value,T,M)<<endl;

delete[] time;

delete[] value;

return 0;

}