HDU2602 Bone Collector（01背包）

01背包模板题。

1维数组倒推。

 1 #include
 2 #include
 3 #include
 4 using namespace std;
 5 #define M 1005
 6 int dp[M];
 7 int val[M],v[M];
 8 
 9 int main(){
10     int t,N,V;
11     cin>>t;
12     while(t--){
13         memset(dp,0,sizeof(dp));
14         cin>>N>>V;
15         for(int i=1;i<=N;i++) cin>>val[i];
16         for(int i=1;i<=N;i++) cin>>v[i];
17         for(int i=1;i<=N;i++)
18             for(int j=V;j>=v[i];j--)
19                 dp[j]=max(dp[j],dp[j-v[i]]+val[i]);
20         cout<endl;
21     }
22     return 0;
23 }