HDU2602 Bone Collector（01背包）

题目链接

01 背包裸题

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[1005];
int w[1005];
int c[1005];
int main(){
    //freopen("a.txt", "r", stdin);
    int t; cin >> t;
    while(t--){
        memset(dp, 0, sizeof(dp));
        int n, v;
        scanf("%d %d", &n, &v);
        for(int i = 1; i <= n; i++){
            scanf("%d", &w[i]);
        }
        for(int i = 1; i <= n; i++){
            scanf("%d", &c[i]);
        }
        //01背包
        for(int i = 1; i <= n; i++){
            for(int j = v; j >= c[i]; j--){
                dp[j] = max(dp[j], dp[j-c[i]]+w[i]);
            }
        }

        cout << dp[v] << endl;
    }
    return 0;
}