题目描述
描述：
给你N个物品的重量和价值，将这些物品放入容量为W的背包中，以获取背包中的最大总价值。请注意，每个项目只有一个数量。
换句话说，给定两个整数数组val [0..N-1]和wt [0..N-1]，它们分别表示与N个物品的重量和价值。还要给定代表背包容量的整数W，找出val []的最大值子集，以使该子集的权重之和小于或等于W。你不能破坏某个物品（比如把物品拆分），只能选择它，或者不要选择它（0-1属性）。
输入：
的第一行包含一个整数T，表示测试用例的数量。然后是 T测试用例。每个测试用例包含四行。
第一行由N个项目组成。
第二行包含W，即背包的最大容量。
在第三行中， N个空格分隔的正整数表示N个物品的价值，
在第四行中，N个空格分隔的正整数表示相应物品的重量。
输出：
对于每个测试用例，在新一行中，输出在给定条件下可以获得的背包最大价值。
动态规划解法
明确问题的状态和选择.
分析题目可以发现问题的状态有两个，背包容量和可选择的物品；对于每个物品，我们在选择时有两种方案：装进背包或者不装进背包，这也是为什么叫做0-1背包问题。
定义dp数组
刚才分析出来问题的状态有两个，因此需要一个二维数组，一维表示可选的物品范围，另一维表示背包的容量。dp[i][j]的定义如下：对于前i个物品，当前背包的容量为j，这种情况下可以装的最大价值是dp[i][j]。
这样我们最终想要的答案就是dp[N][W]。
基础状态：dp[..][j] = 0， 因为可选的物品为空，即背包什么都没有装，价值为零；dp[i][..] = 0，因为背包的容量为零，什么也装不了。
状态转移方程
回顾刚才的分析，状态的改变有两个选择：
对与第i个商品，①不装入背包，那么背包的最大价值dp[i][j]显然是继承dp[i-1][j]，背包的容量和价值都不变。②装入背包，那么背包的最大价值应该是前i-1个物品的最大价值加上第i个商品的价值，换句话说，我们的前提是装第i个物品，也就是在剩余重量w-wt[i-1]限制下能装的最大价值，加上第i个物品的价值val[i-1]，即dp[i][j] = dp[i-1][j-wt[i-1]]+val[i-1]。
注意：物品的价值和重量数组下标从0开始，即wt[i-1]和al[i-1]分别对应第i个物品的重量和价值。
综合一下我们的状态转移方程就是：
代码
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main() {
int t;
cin>>t;
int n,w;
while(t--){
cin >> n >> w;
vector<int> val(n),wt(n);
for(int i = 0; i < n ; ++i){
cin >> val[i];
}
for(int i = 0; i < n ; ++i){
cin >> wt[i];
}
vector<vector<int>> dp(n+1, vector<int>(w+1, 0));
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= w; ++j){
if(j>=wt[i-1]){
dp[i][j] = max(dp[i-1][j-wt[i-1]] + val[i-1], dp[i-1][j]);
}
else dp[i][j] = dp[i-1][j];
}
}
cout << dp[n][w] << endl;
}
return 0;
}复杂度分析：
时间复杂度：O(N*W)
N代表物品的数量，W代表背包的容量。
空间复杂度：O(N*W)
使用一个N*W的二位数组。
