hdu2602——Bone Collector

01背包问题！

1.现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]];

2. f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值.

#include<stdio.h>
#include<string.h>
int a[1005],b[1005];
int f[1005];
int main()
{
    int t,i,j,n,v;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&v);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
            scanf("%d",&b[i]);
        for(i=1;i<=n;i++)
            for(j=v;j>=0;j--)
            {
                if(j-b[i]>=0)
                {
                    f[j]=f[j-b[i]]+a[i]>f[j]?f[j-b[i]]+a[i]:f[j];
                }
                else f[j]=f[j];
            }
            printf("%d\n",f[v]);
    }
}