同样是标准的01背包，题目的解析就不说了

http://www.tsinsen.com/ViewGProblem.page?gpid=A1153

 

 

 

 

* * ===================================================================================== * *       Filename:  noip2005pujizucaiyao.c * *    Description:  RT * *        Version:  1.0 *        Created:  2014-05-19 16:38:04 *       Revision:  none *       Compiler:  gcc * *         Author:  Rainboy (mn), 597872644@qq.com *        Company:  NONE * * ===================================================================================== */#include 
     
      int zongjiazhi[1001]={0};int T,M;int timespend[100],jiazhi[100];int main(int argc, const char *argv[]){    int i,j,k,l;        scanf("%d%d",&T,&M);    for (i = 0; i < M; i++) {        scanf("%d%d",&timespend[i],&jiazhi[i]);    }    for (i = 0; i < M; i++) {        for (j = T; j > 0 ; j--) {            if((timespend[i] <= j) && (jiazhi[i] + zongjiazhi[j-timespend[i]] > zongjiazhi[j]) )                zongjiazhi[j] = jiazhi[i] +zongjiazhi[j-timespend[i]];        }        }    printf("%d\n",zongjiazhi[T]);    return 0;