HDU 2602 Bone Collector

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 int main(){
 8     int T;
 9     cin >> T;
10     while(T--){
11         int N, V;
12         cin >> N>>V;
13         vector<int> value(N), volume(N);
14         for(int i = 0; i < N; i ++) cin >>value[i];
15         for(int i = 0; i < N; i ++) cin >>volume[i];
16         vector<int> dp(V+1,0);
17 
18         for(int i = 0; i < N; i ++ ){
19             for(int j = V; j >= volume[i]; j --){
20                 dp[j] = max(dp[j],dp[j-volume[i]]+value[i]);
21             }
22         }
23         cout<< dp[V]<<endl;
24     }
25     return 0;
26 }