采药 （C语言代码）

解题思路:建议大家看一下0-1背包问题（在这里一时半会也说不清楚，我看了好几天才明白一点，有点笨，哈哈^*_*^），然后利用一维状态转移方程f[i]=max(f[i],f[i-w[j]]+p[j])（也有二维的）;i表示时间轮回，就是把时间从大到小轮流一下带入i

(

for(i=T;i>=w[j];i--)

{

    f[i]=max(f[i],f[i-w[j]]+p[j]);

}

);

f[i]表示已采药草在当前时间下的最优解的价值的最大值，w[j]表示采第j种草药的时间，p[j]表示第j种草药的价值；
注意事项:p[101],w[101]这个一维数组大小一定要注意，如果是p[100],w[100]的话会错的，我找了好久才找到这个错误。。。。。。。

参考代码:

#include<stdio.h>

#define max(a,b) (a)>(b)?(a):(b)//取a,b最大值

int main(int argc, char *argv[])

{

int f[1001]={0};//用来保存时间的数组别忘初始化为0

int i;

int T,M,p[101],w[101],j;

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

for(i=0;i<M;i++)//M循环次数

{

    scanf("%d %d",&w[i],&p[i]);//获得输入值

}

for(j=0;j<M;j++)//开始循环求每一次的最优解，从第一种药草开始循环，一直到最后一种

{

for(i=T;i>=w[j];i--)//i-w[j]必须大于等于0，就为负了，必须倒着循环！

{

    f[i]=max(f[i],f[i-w[j]]+p[j]);//f[i]保存每一次循环后的最优解

}

}

    printf("%d",f[T]);//最后一次循环的最后一个值就是最优解

return 0;

}