采药 （C语言描述——参考01背包问题思路）

解题思路:
参考01背包问题思路。




注意事项:





参考代码:

#include<stdio.h>

void caiyao();

void kaicai(int *value,int *time,int M,int T);

int sumvalue[102][1001];

#define  max(x,y) (x)>(y)?(x):(y)

int main(){

     int T,M,i;

     int value[100],time[100];

     while(scanf("%d%d",&T,&M)!=EOF){

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

          scanf("%d%d",&time[i],&value[i]);

          kaicai(value,time,M,T);

     }

     return 0;

}

void kaicai(int *value,int *time,int M,int T){

   int m,t;

   for(m=1;m<=M;m++){

         for(t=1;t<=T;t++){

         if(time[m]<=t)

             sumvalue[m][t]=max(sumvalue[m-1][t-time[m]]+value[m],sumvalue[m-1][t]);

         else

             sumvalue[m][t]=sumvalue[m-1][t];

      }

   }

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

}