hdu 2602 Bone Collector(0/1背包)

点击打开链接hdu 2602

思路: 裸0/1背包

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
const int MAXN = 1000010;

int n , sum;
int v[N] , w[N] , dp[N];

int solve(){
    memset(dp , 0 , sizeof(dp));
    for(int i = 1 ; i <= n ; i++)
        for(int j = sum ; j >= v[i] ; j--)
            dp[j] = max(dp[j] , dp[j-v[i]]+w[i]);
    return dp[sum];
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
         scanf("%d%d" , &n , &sum);
         for(int i = 1 ; i <= n ; i++)
             scanf("%d" , &w[i]);
         for(int i = 1 ; i <= n ; i++)
             scanf("%d" , &v[i]);
         printf("%d\n" , solve());
    }
    return 0;
}