hdu 寒冰王座

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1248

一开始是知道是完全背包问题的，但是不会完全背包，也不能叫全不会，只是理解了一点，还差一点就会了

刚开始写的时候按照f[i][j]=max(f[i-1][j],f[i-1][j-k*weight[i]]+k*weight[i]);

到后来才知道是直接求里面最大的f[i][j]=max(f[i-1][j-k*weight[i]]+k*weight[i]);

用个max变量存最大的，然后赋值给f[i][j]

代码如下:

#include <stdio.h>
#include <string.h>
int f[5][10005];int main(){int a[3]={150,200,350},b,c,d,i,j,k,n,m,max;scanf("%d",&n);while(n--){scanf("%d",&m);memset(f[0],0,sizeof(f[0]));for(i=1;i<=3;i++){for(j=150;j<=m;j++){max=0;for(k=0;j-k*a[i-1]>=0;k++)if(f[i-1][j-k*a[i-1]]+k*a[i-1]>max)max=f[i-1][j-k*a[i-1]]+k*a[i-1];f[i][j]=max;}}printf("%d\n",m-f[3][m]);}}