- 划分阶段：
背包容量恒定（是一个集合）， 每⼀件物品只选一次且该物品只有选或者不选两种状态，那么我们可以划分阶段为在背包容量为maxw的情况下，可以选择几件物品且其总价值最大
- 确定状态：
使用二维数组dp[i][j]表示将前i件物品放进限重为j的背包可以获得的最大价值
0<=i<=n、0<=j<=maxn
- 状态转移方程：
最大容量是一步步推导出来的，并非看题就会，要先分析：
==dp的初始化：==当选择i=0件物品时，背包容量j从0增到maxn时dp[0][j]=0;
假设选择了i,j点，那么dp[i][j]是怎么来的呢?
首先保证选择的重量w[i]要小于背包的待选总容量，然后当前物品分为装入和不装入两种状态
| 容量1 | 容量2 | 容量3 | 容量4 | |
|---|---|---|---|---|
| 物品1（1-15） | 15 | 15 | 15 | 15 |
| 物品2（3-20） | 15 | 15 | 20 | 35 |
| 物品3（4-30） | 15 | 15 | 20 | 35 |
-
不装入：
dp[i][j]=dp[i-1][j];
为什么是dp[i-1]，而不是dp[j-1]，注意参考依据是物品的容量在限重的情况下物品是否装入
当物品不能放入时，在该容量下，我们选择的还是上一件物品的状态（容量恒定为j，价值选i-1个的最大价值）
-
装入：
dp[i][j]=v[i]+dp[i-1][j-w[i]];
选即表示当前的物品必选,也就是当前的价值v[i]，那么该物品的容量w[i]就必须保证可以选中，
在当前容量必选的情况下，我们选取前面的物品时就需要注意他们加起来的和必须小于总容量，也就是上一个状态的容量dp[i-1][?]+该物品的容量w[i]必须小于等于当前选择的背包总容量j；得出上一个状态的容量要选j-w[i]
即装入的状态
-
状态转移方程为：
dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]); // j >= w[i] -
使用递推求解：
使用嵌套循环
外循环先遍历物品，然后内循环遍历背包重量
最后一个值便是结果