开心的金明 （C语言代码）

解题思路:

背包问题



注意事项:





参考代码:

#include<stdio.h>

int sum[25][30100]; 

int max(int a,int b)

{

if(a>b)

{

return a;

}

else

return b;

}

int main()

{

int i,m,N,v,w,j;

scanf("%d%d",&N,&m);

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

{

scanf("%d%d",&v,&w);

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

{

sum[i][j]=sum[i-1][j];//i不能等于0，i-1； 

}

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

{

if(j+v<=N)

{

sum[i][j+v]=max(sum[i-1][j+v],sum[i-1][j]+v*w);

}

}

}

printf("%d",sum[m][N]);

}