01 背包题目分析
有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是 O(2^n)，这里的 n 表示物品数量。
暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！
在下面的讲解，举一个例子：
| 重量 | 价值 | |
|---|---|---|
| 物品 0 | 1 | 15 |
| 物品 1 | 3 | 20 |
| 物品 2 | 4 | 30 |
01 背包解决方法
递归五部曲
- 确定 dp 数组以及下标的含义：dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。
为什么需要用二维数组呢？因为有两个维度需要分别表示：物品和背包容量。
我们先看把物品 0 放入背包的情况：
背包容量为 0，放不下物品 0 或者物品 1，此时背包里的价值为 0。
背包容量为 1，只能放下物品 0，背包里的价值为 15。
背包容量为 2，只能放下物品 0，背包里的价值为 15。
背包容量为 3，上一行同一状态，背包只能放物品 0，这次也可以选择物品 1 了，背包可以放物品 1 或者物品 0，物品 1 价值更大，背包里的价值为 20。
背包容量为 4，上一行同一状态，背包只能放物品 0，这次也可以选择物品 1 了，背包可以放下物品 0 和物品 1，背包价值为 35。
- 确定递推公式
对于递推公式，首先我们要明确有哪些方向可以推导出 dp[i][j]。
这里我们 dp[1][4] 的状态来举例：
求取 dp[1][4] 有两种情况：
- 放物品 1
- 还是不放物品 1
如果不放物品 1，那么背包的价值应该是 dp[0][4] 即容量为 4 的背包，只放物品 0 的情况。
如果放物品 1，那么背包要先留出物品 1 的容量，目前容量是 4，物品 1 的容量（就是物品 1 的重量）为 3，此时背包剩下容量为 1。
容量为 1，只考虑放物品 0 的最大价值是 dp[0][1]，这个值我们之前就计算过。
所以放物品 1 的情况 = dp[0][1] + 物品 1 的价值。
两种情况综合一起可以得出：
递归公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
- dp 数组初始化
首先从 dp[i][j] 的定义出发，如果背包容量 j 为 0 的话，即 dp[i][0]，无论是选取哪些物品，背包价值总和一定为 0。
从递归公式可以看出 i 是由 i-1 推导出来，那么 i 为 0 的时候就一定要初始化。
- 确定遍历顺序
先遍历物品还是先遍历背包重量呢？
其实都可以！但是先遍历物品更好理解。
那么我先给出先遍历物品，然后遍历背包重量的代码。
for(int i = 1; i < n; i++) {
for(int j ; j <= bagweight; j++) {
(j < weight[i]) {
dp[i][j] = dp[i - ][j];
} {
dp[i][j] = Math.max(dp[i - ][j], dp[i - ][j - weight[i]] + value[i]);
}
}
}
