hdu 2602 Bone Collector（我的第一个01背包）

Bone Collector

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7904????Accepted Submission(s): 2949

???????????? ?for v=V..0

????????????????? f[v]=max{f[v],f[v-c[i]]+w[i]};

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

代码：

#include <iostream>#include <stdio.h>#include <memory.h>using namespace std;int c[1005], w[1005];int bag[1005];int N, V;void _01_bag()  //01背包：逆序！{    int i, j;    memset(bag, 0, sizeof(bag));    for(i = 0; i < N; i++)    {        for(j = V; j >= c[i]; j--)        {            bag[j] = max(bag[j], bag[j-c[i]] + w[i]);        }    }}int main(){    int i, t;    scanf("%d", &t);    while(t--)    {        scanf("%d %d", &N, &V);        for(i = 0; i < N; i++)            scanf("%d", &w[i]);        for(i = 0; i < N; i++)            scanf("%d", &c[i]);        _01_bag();        printf("%d\n", bag[V]);    }    return 0;}

?