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 放入背包的情况：
再看把物品 1 放入背包：
背包容量为 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 的情况。
