1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 const int maxn=1005;
 7 
 8 int dp[maxn][maxn];
 9 
10 int va[maxn],vo[maxn];
11 
12 int getmax(int a,int b)
13 {
14     if(a>=b)
15         return a;
16     else
17         return b;
18 }
19 
20 int main()
21 {
22     int n,all;
23     int t;
24     cin>>t;
25     while(t--){
26         cin>>n>>all;
27         for(int i=1;i<=n;i++)
28             cin>>va[i];
29         for(int i=1;i<=n;i++)
30             cin>>vo[i];
31         for(int i=0;i<=n;i++)
32             dp[i][0]=0;
33         for(int j=0;j<=all;j++)
34             dp[0][j]=0;
35         for(int i=1;i<=n;i++)
36         {
37             for(int j=0;j<=all;j++)
38             {
39 
40                     if(j-vo[i]<0)
41                         dp[i][j]=dp[i-1][j];
42                     else
43                         dp[i][j]=getmax(dp[i-1][j],dp[i-1][j-vo[i]]+va[i]);
44 
45             }
46         }
47         for(int i=0;i<=n;i++)
48         {
49             for(int j=0;j<=all;j++)
50             {
51                 cout<<dp[i][j]<<" ";
52             }
53             cout<<endl;
54         }
55         cout<<dp[n][all]<<endl;
56     }
57     return 0;
58 }

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 int dp[1001];
 6 int vo[1001];
 7 int va[1001];
 8 
 9 int main()
10 {
11     int n,all;
12     int t;
13     cin>>t;
14     while(t--)
15     {
16         memset(dp,0,sizeof(dp));
17 
18         cin>>n>>all;
19         for(int i=1;i<=n;i++)
20             cin>>va[i];
21         for(int i=1;i<=n;i++)
22             cin>>vo[i];
23         for(int i=1;i<=n;i++)
24         {
25             for(int j=all;j>=0;j--)
26             {
27                 if(j-vo[i]>=0)
28                 dp[j]=max(dp[j],dp[j-vo[i]]+va[i]);
29             }
30         }
31         cout<<dp[all]<<endl;
32     }
33     return 0;
34 }

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 const int maxn=1001;
 6 
 7 int va[maxn],vo[maxn],dp[maxn][maxn];
 8 
 9 int ddp(int i,int v)
10 {
11     if(dp[i][v]!=-1)
12         return dp[i][v];
13     if(i==0||v==0)
14         return dp[i][v]=0;
15     if(v-vo[i]>=0)
16         return dp[i][v]=max(ddp(i-1,v),ddp(i-1,v-vo[i])+va[i]);
17     else
18         return dp[i][v]=ddp(i-1,v);
19 }
20 
21 int main()
22 {
23     int n,all;
24     int t;
25     cin>>t;
26     while(t--)
27     {
28         cin>>n>>all;
29         for(int i=1;i<=n;i++)
30             cin>>va[i];
31         for(int i=1;i<=n;i++)
32             cin>>vo[i];
33         memset(dp,-1,sizeof(dp));
34         cout<<ddp(n,all)<<endl;
35     }
36     return 0;
37 }