蓝桥杯算法训练VIP-入学考试 （C语言代码）

解题思路:动态规划的基础内容，不会去看动态规划





注意事项:





参考代码:

#include<stdio.h>

void main()

{

int T,M,i,j;

int shuz[110][1010],cyao[101][2];

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

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

scanf("%d%d",&cyao[i][1],&cyao[i][0]);

for(i=0;i<=T;i++)

{

if(i<cyao[0][1])shuz[0][i]=0;

else{ shuz[0][i]=cyao[0][0]; }

}

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

{

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

{

if(j<cyao[i][1])

{ shuz[i][j]=shuz[i-1][j];}

else{

if( (shuz[i-1][j-cyao[i][1]]+cyao[i][0]) >= shuz[i-1][j] )

{ shuz[i][j]=shuz[i-1][j-cyao[i][1]]+cyao[i][0]; } 

else{ shuz[i][j]=shuz[i-1][j]; }

}

}

}

printf("%d\n",shuz[M-1][T]);

}