首先我们需要知道什么是0-1背包问题。 即N件物品和最多能承受重量W的背包，第i件物品的重量为Weight[i]，价值为Value[i]。每件物品只能使用一次，求解将那些物品放入背包能使价值最大。这就是标准的0-1背包问题。 ## 1.暴力解法 暴力解法很容易想到，对于每个物品只有放进背包和不放进背包两种选择，因此只要使用回溯法搜索出每种情况就好，因此时间复杂度为O(2^N)，这是指数级别的时间复杂度，显然我们需要更好的算法来进行优化。 ## 2.二维动态数组 ### 2.1确定动态数组及其下标的含义 dp[i][j]代表从[0,i]个物品中选取任意个物品，使得承受重量为j的背包价值最大。 ### 2.2确定递推公式 首先确定一个方向，即从物品的方向进行推理，即我们要从第dp[i-1]递推到dp[i]。
- 第一种情况，如果weight[i]>j，显然第i件就不可能被放进背包，于是得到dp[i][j] = dp[i-1][j]
- 第二种情况，如果weight[i]<=j，那么此时第i件物品就有被放进背包的可能，但是不是一定的，因为把背包剩余空间不一定够，那么把其他物品放出来就可能使价值减小。当然，也有可能空间足够，或者把其他物品放出来，第i件物品放进去不会使背包价值减小。我们只要取两种可能的最大值即可。于是得到dp[i][j]
= max(dp[i-1][j]，dp[i-1][j-weight[i]]+value[i]) ### 2.3dp数组初始化 当j
= 0时，显然不可能有物品能放入背包，所以dp[i][0] = 0。 当i =
0时，只要此时的j>=weight[i]，背包的价值即为value[0]，即对于符合条件dp[0][j]
= value[0]。
由于物品的价值一定大于0（通常情况下），并且dp代表背包价值的最大值。所以对其他元素初始化为0即可，不会影响dp的后续取值。
### 2.4确定遍历顺序 先i后j和先j后i都可以，具体代码比如 以上就是对0-1背包问题的简单分析。值得注意的是0-1背包是经典的【NP完全问题】，我们不应该期待他有多项式级复杂度以内的解法，所以排序后贪心等想法都可以不再考虑。 ## 3.实际问题转化为0-1背包问题
1
2
3
4
5
6
7
8// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 这个是为了展现dp数组里元素的变化
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
0-1背包问题是i个物品，重量小于j，且价值最大。这道问题可以解释成i个数字，相加起来等于j。与0-1背包问题类似，可以使用二维dp的方法