二维数组

  1. dp[i][j] 的含义：大小为j的背包，放下标为[0 - i]的物品时的最大价值
  2. 初始化：
    1. dp[i][0]不能放任何东西，初始化为0；
    2. dp[0][j]只能放下标为0的物品，因此只要背包大小比0号物品大了，那么就赋值value[0]；
    3. 其余位置都可以随便赋值，因为其余位置都是根据左上角或者正上方计算得到的
  3. 转移方程：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  4. 遍历顺序：既可以外层物品内层背包大小，也可以反过来 ```java // weight数组的大小 就是物品个数 for(int i = 1; i < weight.size(); i++) { // 遍历物品 for(int j = 0; j <= bagweight; j++) { // 遍历背包容量

    1.  if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
    2.  else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    } }

for(int j = 0; j <= bagweight; j++) { // 遍历背包容量 for(int i = 1; i < weight.size(); i++) { // 遍历物品 if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } }

  3. <a name="mQXH9"></a>
  4. # 滚动数组
  6. 1. dp[j] 的含义：大小为j的背包存放物品后的最大价值
  7. 1. 转移方程：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
  8. 1. 初始化：dp[0]肯定是0，非0下标也应该设置为0，因为递推公式中本层的dp[j]也会被用到，如果设置得大了会覆盖掉实际值
  9. 1. 遍历顺序：
  10.    1. 只能外层物品，内层背包，反过来的话每个dp[j]都只会放入一个物品
  11.    1. 内层遍历背包时一定要倒序遍历，否则会重复加入同一下标的物品
  12. ```java
  13. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  14.     for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
  15.         dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
  17.     }
  18. }

应用

  1. 分割等和子集

背包大小：sum/2
dp[i] : 容量为i的背包最大可以凑成的总和
转移方程：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

  1. 最后一块石头的重量

背包大小：sum/2
dp[i]：容量为i的背包最多能放dp[i]重量的石头
转移方程：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

  1. 目标和

背包大小：
列方程：left + right = sum, left - right = target
推出left = (target + sum) / 2
dp[i]：装满i这么大容量的背包，有dp[i]种解法
初始化：dp[0] = 1
转移方程：dp[j] += dp[j - nums[i]]

  1. 一和零

背包是二维的数组，但是本质上还是0-1背包问题