简单01背包
状态转移方程 dp[j] = max{dp[j], dp[j - volume[i]] + value[i]};
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #define mem(a) memset(a, 0, sizeof(a)) 5 using namespace std; 6 const int maxn = 1050; 7 int dp[maxn]; 8 int value[maxn]; int volume[maxn]; 9 int main() 10 { 11 int T; cin >> T; 12 while(T--) { 13 int n, v; 14 cin >> n >> v; 15 for(int i = 1 ; i <= n ; i++) cin >> value[i]; 16 for(int i = 1 ; i <= n ; i++) cin >> volume[i]; 17 mem(dp); 18 for(int i = 1 ; i <= n ; i++) 19 for(int j = v ; j >= volume[i] ; j--) 20 dp[j] = max(dp[j - 1], dp[j - volume[i]] + value[i]); 21 cout << dp[v] << endl; 22 } 23 return 0; 24 }