典型的01背包
#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<map> #include<queue> #include<cmath> #include<stack> #include<vector> #include<cstdio> #define MAXN 33000 #define INF 0x3f3f3f3f #define lmid l,m,rt<<1 #define rmid m+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 #define Mod 1000000007 #define i64 __int64 using namespace std; int x[1005],y[1005]; int dp[1005]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&x[i]); for(int i=0;i<n;i++) scanf("%d",&y[i]); memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) for(int j=m;j>=y[i];j--) { dp[j]=max(dp[j],dp[j-y[i]]+x[i]); } cout<<dp[m]<<endl; } }