hdu2602

这题就是一题十分简单明了的01背包问题。直接用01背包的函数就可以AC出来了。

最优解方程：f[j]=max(f[j],f[j-c[i]]+w[i])

十分简单的一题。不过因为太简单了，楼主在A的时候把输入的物体价值和体积写反了，然后一直找不出问题。

所以看题是十分重要的一件事情 。磨刀不误砍柴工。

题目：

http://acm.hdu.edu.cn/showproblem.php?pid=2602

#include <iostream>
#include <stdio.h>
int f[1005];
int c[1005],w[1005];
int max(int a,int b)
{
    if(a>b)return a;
    else return b;
}

int main()
{
    int T,N,V,i,j;
    scanf("%d",&T);
    while(T--)
    {
        memset(f,0,sizeof(f));
        memset(c,0,sizeof(c));
        memset(w,0,sizeof(w));
        scanf("%d%d",&N,&V);
        for(i=1;i<=N;i++)
            scanf("%d",&w[i]);
        for(j=1;j<=N;j++)
            scanf("%d",&c[j]);
        for(i=1;i<=N;i++)
        {
            for(j=V;j>=c[i];j--)
            {
               f[j]=max(f[j],f[j-c[i]]+w[i]);
            }
        }
        printf("%d\n",f[V]);
    }
    return 0;
}

楼主好好人的，这里给你们附上两组数据，可以测试一下：

2

5 0

1 2 3 4 5

0 0 1 0 0

3 2

1 2 3

3 2 1

答案：12

3