采药 （C语言代码）

解题思路:这个题充分考察了算法的能力，实际上就是01背包的一个非常简单的变形，如果可以我建议先百度一下01背包，再来看这个问题就会容易的多了。

运用到的知识：

多维数组，递归（知道为什么不好做了吧(￣▽￣)"

注意事项:一定要注意数组的范围！！！题主就是在这个非常平常的地方栽了跟头。。。哭4

参考代码:

int max(int a,int b)
{
 return a>b?a:b;
}

int main()
{
 int T,M,t[101],c[101];  //t[101]储存每一个药的时间，c[101]储存每一个药价值
 int f[102][1002]={0};  //务必初始化，其实呢也可以只用把二维数组的第一行初始化就ok了
 int i,j,k;
 scanf("%d %d",&T,&M);
 for(i=1;i<=M;i++)
 {
  scanf("%d %d",&t[i],&c[i]);
 }
 for(i=1;i<=M;i++)
 {
  for(j=1;j<=T;j++)
  {
   if(j>=t[i])
   f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+c[i]);  //这就是01背包中的两个状态，采或者不采两种情况哪个的价值最大
   else
   f[i][j]=f[i-1][j];    //书包的空间（时间不够了）
   
  }
 }
 for(i=0;i<=M;i++)            //检查所有的值，找最大的值
 {
  k=f[0][0];
  for(j=0;j<=T;j++)
  {
   if(f[i][j]>k)
   k=f[i][j];
  }
 }
 printf("%d",k);
 }

//其实呢，除了多维数组，一维数组利用递归也是可以解决问题滴

//不过，悲惨的超时了。。。。

int t[100],c[100];
 int main()
 {
  int T,M,k,i;
  scanf("%d %d",&T,&M);
  for(i=1;i<=M;i++)
{
   scanf("%d %d",&t[i],&c[i]);
}
  int make(int ,int );
  k=make(M,T);
  printf("%d",k);
  return 0;
  }
 int make(int i,int j)    //第 i个对象，剩余j个时间
 {
 

   if(i==0)
   return 0;
   if(j>=t[i])
   {
    int r1=make(i-1,j);
    int r2=make(i-1,j-t[i])+c[i];
    return r1>r2?r1:r2;
    
   }
   else return make(i-1,j);
 }