0-1背包

#include <stdio.h>
#include <string.h>
int f[1001][1001];
int c[1001];
int w[1001];
int N,V;
int main()
{
    int t;
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        scanf("%d%d",&N,&V);
        for(i = 1;i<=N;i++)
        {
            scanf("%d",&w[i]);
        }
        for(i = 1;i<=N;i++)
        {
            scanf("%d",&c[i]);
        }
        for(i = 1;i<=N;i++)
        {
            for(j = 0;j<=V;j++)
            {
                if(j>=c[i])
                {
                    if(f[i-1][j]<f[i-1][j-c[i]] + w[i])
                    {
                        f[i][j] = f[i-1][j-c[i]] + w[i];
                    }
                    else
                    {
                        f[i][j] = f[i-1][j];
                    }
                }
                else
                    f[i][j] = f[i-1][j];
            }
        }
        printf("%d\n",f[N][V]);
    }
}

0-1背包,布布扣,bubuko.com

0-1背包

原文：http://www.cnblogs.com/yangyongqian/p/3877986.html