采药 （C语言代码）

解题思路:01背包+动态规划  思想可以网上找

注意事项:

参考代码:

#include <stdio.h>

int max(int a,int b);

int main()

{

int T,M,i,j;

int herbt[101];//存储采每种草药所需的时间 

int herbv[101];//存储每种草药的价值 

int m[101][1001];//动态存储最大价值矩阵 

scanf("%d%d",&T,&M);

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

{

scanf("%d%d",&herbt[i],&herbv[i]);

}

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

{

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

{

if(j>=herbt[i])

m[i][j]=max(m[i-1][j],(m[i-1][j-herbt[i]]+herbv[i]));

else

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

}

}

//面对第i种草药，有时间j（不是剩余时间j）的时候，是采还是不采？如果j<herbt[i](采这种草药需要的时间)，肯定采不了，m[i][j]=m[i-1][j]; 如果j>=herbt[i],就要看采了它是否会带来更大的价值，

// 把herbt[i]的时间腾出来，看采了i之后的价值 m[i-1][j-herbt[i]]+herbv[i]和之前的 m[i-1][j]谁大，选更大的赋值给m[i][j] 

printf("%d\n",m[M][T]);

return 0;

}

int max(int a,int b)

{

if(a>=b)

return a;

else

return b;

}