HDOJ_2602 0/1背包问题

背包问题里面最基础的0 1背包问题，就是讲放或者不放的问题。其基本思想是，先放一个权值，然后用剩余的空间来放其他的，更新这时全部的能量状态，然后放两个，这时是 根据第一次的各权值状态来更新本次能量状态....依次类推

#include<stdio.h>
#include<string.h>
int max(int a,int b)
{
    return a>=b?a:b;
}
int main()
{
    int T,n,m,i,j,f[1010],a[1010],v[1010];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;++i)
            scanf("%d",&a[i]);
        for(i=1;i<=n;++i)
            scanf("%d",&v[i]);
        memset(f,0,sizeof(f));
        for(i=1;i<=n;++i)///从1到n 来一个一个更新
            for(j=m;j>=v[i];j--)  //一般是从后向前推，其意义是，从总数里面一点点的减，直到当前值。
                f[j]=max(f[j],f[j-v[i]]+a[i]);/////记者里面是减去用掉的空间，后面加上 对应权值
        printf("%d\n",f[m]);
    }
    return 0;
}