hdu2602——Bone Collector

44424742

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]);    }}