有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求背包放哪些物品后价值最大。 ps:weight数组的大小 就是物品个数
[](()题解
1，设dp[i][j]表示从下标[0~i]的物品中任取，放到容量为j的背包中的最大总价值；
2，转移方程：（两种情况）
2.1，背包放不下物品 i 时（此时物品i的重量大于背包容量j）
dp[i][j] = dp[i - 1][j];
2.2，背包可以放下物品 i 时
dp[i][j] = dp[i - 1][j - wight[i]] + value[i];
//dp[i - 1][j - wight[i]]是背包不放i时的最大价值
3，初始化
3.1，当 j 为零时，即背包容量为零，此时什么物品都放不下，所以价值为零，即dp[i][0] = 0；
3.2，当 i 为零时，即背包在不同容量下放编号为0的物品的最大价值，此时需要一个循环进行初始化；
for (int j = bagSize; j >= weight[0]; j--) {
dp[0][j] = dp[0][j - weight[0]] + value[0];
}
这里就有一个关键点了，为什么这里循环要用倒序遍历呢？
如果正序的话就会出现一个问题，在遍历过程中0号物品会被加很多次，因为每次不同容量下的背包 j 的最大价值总需要加上前一个容量 j-wight[0] 的背包的最大价值，这就造成了value[0]被重复相加，而我们只想每个容量下的value[0]只会加一次（可以举个例子试试）
而倒序就不会出现这个问题，因为从最大的开始，前一个最大价值总为0，所以只需要加上当前物品的最大价值value[i]即可；
总的来说就是要保证物品0在不同容量下只被放入一次
4，遍历顺序
最后我们需要考虑一下到底是先遍历物品 i 还是先遍历背包重量 j ？
其实这里谁先谁后都可以，没有什么区别；
代码如下：
int bagProblem1(vector<int> weight, vector<int> value, int bagsize) {
vector<vector<int>> dp(weight.size() + 1, vector<int>(bagsize + 1, 0));
for (int j = bagsize; j >= weight[0]; j--) {
dp[0][j] = dp[0][j - weight[0]] + value[0];
}
for(int i = 1; i < weight.size(); i++) { // 遍历每一件物品
for(int j = 0; j <= bagsize; j++) { // 遍历不同的背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
return dp[weight.size() - 1][bagsize]
}
当然这个代码对空间还可以优化一下，运用一个滚动数组，将dp二维降到一维，下面我们看看实现方式；
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);从中我们可以发现每次我们只需要dp[i][j]和dp[i - 1][j]，即可以写成
dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);这时这个二维数组是不是就可以化为一维数组了；
接下来我们开始分析：
1，dp[j]表示容量为 j 的背包，所背的物品价值可以最大为dp[j]。
2，转移方程：
这时dp[j]有两个选择，一个是取自己dp[j]，一个是取dp[j - weight[i]] + value[i]，所以转移方程就是：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3，初始化：
当背包容量 j 为零时，放不下任何东西，所以最大价值为0，
因为我们物品价值都是为正的，所以初始状态都设为0即可；
4，遍历顺序
这就和二维的有些不同了，这里遍历顺序是固定的，即外层是物品数目 i ，里面是容量 j ，为什么要这样呢？
这是为了保证每个物品都可以在不同容量的背包存一次，反过来说，如果遍历顺序相反，就会造成每种容量下的背包dp[j]只会存放一个物品；
还有一点是背包容量 j 的遍历同样需要从大到小，和二维初始化原理一样，只有从大到小才能保证物品 i 在一个容量 j 下只会被放入一次。
代码如下：
int bagProblem(vector<int> weight, vector<int> value, int bagsize) {
vector<int> dp(bagsize + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历每一件物品
for(int j = bagsize; j >= weight[i]; j--) { // 遍历不同的背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[bagsize];