HDOJ(HDU).2602 Bone Collector (DP 01背包）

题意分析

01背包的裸题

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 1005

using namespace std;

int v[nmax],w[nmax],dp[nmax];

int main()

{

    //freopen("in.txt","r",stdin);

    int t;

    scanf("%d",&t);

    while(t--){

        memset(dp,0,sizeof(dp));

        int W,N;

        scanf("%d%d",&N,&W);

        for(int i =1; i<=N;++i) scanf("%d",&v[i]);

        for(int i =1; i<=N;++i) scanf("%d",&w[i]);

        for(int i =1; i<=N;++i){

            for(int j = W; j>=w[i];--j)

                dp[j] = max(dp[j],dp[j-w[i]]+v[i]);

        }

        printf("%d\n",dp[W]);

    }

    return 0;

}