1、01背包
【模板】01背包_牛客题霸_牛客网 (nowcoder.com)
1、1可以不装满
背包问题本质上还是一个线性dp。对于物品还是从1选到n。
1、状态表示：
经验 + 题目要求：
dp[i]表示：从前i个物品中选，所有选法中，能挑选出来的最大价值。
但是如果像这样表示dp的话，我们其实是无法解决问题的。
因为，考虑是否选取当前物品的时候，我们必须要考虑到当前背包的剩余容量，并且如果放入当前物品之后，还需要用到前面的dp状态。
所以应该：dp[i][j]：从前i个物品中挑选，总体积不超过j，所有选法中，能挑选出来的最大价值。
2、状态转移方程：
根据最后一步的状况，分情况讨论。
从1号物品，选择到i号物品。那么对于最后一个位置的i号物品，就是两种情况：选或不选
情况1：
不选i物品：那么尽管走到i，但是是从1 ~ i-1个物品中选取，并且此时j还是j。则dp[i][j] = dp[i-1][j]。
情况2：
选i物品：那么选上i物品后，就需要从1 ~ i-1物品中选取物品，但是此时不应该超过的体积 = j - w[i]，w[i]代表i号物品的体积。那么此时dp[i][j] = v[i] + dp[i-1][j - w[i] ]。
但是对于选i物品，需要考虑当前j是否能够容纳i号物品，即判断是否有 j >= w[i]。
即综上：dp[i][j] = max { dp[i-1][j] , v[i] + dp[i-1][ j-w[i] ] }。
3、初始化：
同样，我们多一行一列，方便填表。
保证第一行第一列正确：
第一列：j = 0，背包容量为0，那么此时最大价值0，则第一列0。
第一行：i = 0，0个物品，则最大价值为0，第一行0。
4、填表顺序：
由状态转移方程可知：dp[i][j]受上方dp的状态影响，以及左上方dp状态的影响。
则从上往下填表即可。
5、返回值：
dp[n][V]。
1、2、必须装满
1、状态表示：
dp[i][j]表示：从前i个物品中选取，装满容量为j的背包，所有方法中，能挑选出的最大价值。
2、状态转移方程：
这里约定：如果无法从前i个物品中挑选，正好装满j容量背包的话，dp[i][j] = -1。
为什么不约定为0呢。
因为对于dp[0][0] = 0，表示没有物品挑选，但是也是装满了容量为0的背包，所以此时价值为0。这里就和dp[0][0]作出区分。
那么其实这里的状态转移方程仍然没变：
不选i：dp[i][j] = dp[i-1][j]。即无论dp[i-1][j]是否有挑选方法，都赋值给dp[i][j]。
选i：dp[i][j] = v[i] + dp[i-1][j - w[i] ]。但是这种情况必须判断两个东西：j - w[i] >= 0，并且dp[i-1][j - w[i] ]不等于-1。必须判断在j -w[i]的容量下，是否有挑选方法。不然，后面在max中，如果j -w[i]容量下没有挑选方法，但是仍然会取到v[i] + dp[i-1][j - w[i] ]，因为v[i] + dp[i-1][j - w[i] ]肯定比-1大。
但是如果j -w[i]容量下没有挑选方法，那么整体也是没有挑选方法的。
dp[i][j] = max { dp[i-1][j] , v[i] + dp[i-1][ j-w[i] ] }。
3、初始化：
将dp[0][0] = 0。
第一行 为-1（因为没有物品，无法凑满体积为j的背包，j≠0）。
第一列 为0（不选物品，也是凑满了体积为0的背包）。
4、填表顺序不变。
5、返回值不变。
#include<iostream>
using namespace std;
const int N = 1010;
i
