0-1 背包问题

定义：题目中的物品不可以分割，要么装进包⾥，要么不装， 不能说切成两块装⼀半。-------- 0-1 背包

题目：
给你⼀个可装载N 个物品和重量为 W 的背包 ，每个物品有重量和价值两个属性。其中第 i 个物品的重量为wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

限定的就是容量，求的就是价值！

如：即背包可放三个物品，最大容量为4，求最大重量？
限定的是容量即W，求的是重量即val ；
N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]

• 状态和选择：
  1.状态：
  状态有两个，就是「可选择的物品 N(i) 」和「背包的容量 W」；
  2.选择：
  选择就是「装进背包」或者「不装进背包」；

• dp数组定义：
  dp[i][w] 的定义如下：对于前 i 个物品进行选择，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]，根据这个定义，所求的最终答案就是 dp[N][W]。
  如：dp[3][5] = 6，其含义为：对于给定的⼀系列物品中，若只对前 3 个物品进⾏选择，【当背包容量为 5 时】，最多可以装下的价值为 6。

• basecase：
  base case 就是 dp[0][…] = dp[…][0] = 0，即没有物品和没有容量时，背包装的价值为0；

• 状态转移：
  第一层for：遍历每个物品 i ，判断是否装入
  第二层for：遍历每种w容量约束的；
  状态转移：
  1.如果没有把这第 i 个物品装入背包，那么最大价值 dp[i][w] = dp[i-1][w]，继承上次的结果；
  2.如果把这第 i 个物品装入了背包，那么 dp[i][w] =val[i-1] + dp[i-1][w - wt[i-1]]， 即容量减少，价值可能增加；
  即前i-1个物品相当于放到了容量为 w - wt[i-1]]的背包里！

注意：由于wt[] 和 val[ ] 数组索引从 0 开始，⽽定义dp数组中的 i 是从 1 开始计数的，所以 val[i-1] 和 wt[i-1] 表示第 i 个物品的价值和重量;

框架：
选择：放进背包和不放进背包 ；

如果当前容量w小于当前 i 物品所需的容量wt[i]，则一定不放入背包；

注意：

1. dp的物品数量N和当前容量W是从1开始记数！ 而wt[ ] 和val[ ] 是从0开始记数的！所以 遍历状态时，物品个数 i 从1开始到 N， 容量 w 从1开始到W；
2. dp[][]中，i=0是base case，dp[0][…]和dp[…][0]必须为0，所以 i 从1 开始；
3. 初始化dp 是dp[N+1][W+1] !