01背包问题

基本概念

背包问题是动态规划中的一个经典分支，典型的背包问题就是给定一个有容量上限的背包，再给定一系列的物品，每个物品都有其重量和价值。要求在放入背包的物品重量不超过背包容量上限的条件下，获得最大的价值。

以上是背包问题的基本概念，根据拿取物品的规则不同（每个物品只能拿一个，或可以拿多个等）背包问题又可以细分为多个类别。此处只关注基础的两种背包问题，即01背包和完全背包。

如上图所示，根据物品数量，能拿几个，物品是否分组三个条件扩展出五类背包问题。

此处只关注01背包和完全背包。

01背包：每个物品只能拿一个

完全背包：每个物品能拿若干个

基础实现

01背包二维dp

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

按照动态规划的5个步骤来思考问题

确定dp数组的含义

01背包是二维动态规划， dp[i][j] 表示的含义是从0-i这些物品中选择，放入容量为j的背包的最大价值是多少

确定递推公式

对第i件物品来说，只有放入和不放入两种情况。

如果不放入i，则当前最大值dp[i][j] 就是上一件的最大值即 dp[i-1][j]

如果放入i，则首先需要的容量为weight[i]，这个需要从当前容量j中扣除，即j-weight[i]，那么放入i能获得的最大价值就是容量为j-weight[i]并且不放入i的最大价值加上i的价值即dp[i - 1][j - weight[i]] + value[i]

因此，最终的递推公式为 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

初始化dp

从含义思考，如果背包容量为0，那价值一定是0，所以dp[i][0] = 0;

如果只有第一件商品（i=0），则背包容量大于第一件重量的部分能获得的价值为第一件的价值，其他为0。

由于初始化二维数组的默认值为0，因此只需要将dp[0][j>=weight[i]]的部分赋值value[0]就可以了

for(int j=weight[0];j<=bagSize;j++){
  dp[0][j] = value[0];
}

遍历顺序

遍历物品比较好理解，因此从物品角度出发，每次新增一个物品，在此情况下，遍历背包容量从0到最大能取得的最大值。

for(int i=0;i<weight.size();i++){
  for(int j=0;j<=bagSize;j++){
    if(j<weight[i]) dp[i][j] = dp[i-1][j];
    else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  }
}

最终结果位置

根据dp定义，很好理解，最终结果一定是dp[n-1]bagSize

完整代码

public int getMax01Bag(int[] weight, int[] value, int bagSize){
        // 创建dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods][bagSize + 1];
        // 初始化dp数组
        // 创建数组后，其中默认的值就是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }
        // 填充dp数组
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    /**
                     * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
                     * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                     */
                    dp[i][j] = dp[i-1][j];
                } else {
                    /**
                     * 当前背包的容量可以放下物品i
                     * 那么此时分两种情况：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比较这两种情况下，哪种背包中物品的最大价值最大
                     */
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
            return dp[goods-1][bagSize];
        }

01背包一维数组dp

从上面的递推公式出发，dp[i][j]的两种可能的取值分别为dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]。注意到关于i，只用到了i-1这一层，i-2，i-3等等都是不会再用的，这种情况下，是可以进行压缩的，即用一个一维数组来维护，下一次更新时读到的值刚好就是上一次的值，再之前的值都是没用的。

基于此，重新考虑动态规划五个步骤

确定dp数组的含义

此时dp[j]表示的就是容量为j的背包，所背的物品价值可以最大为dp[j]。（i被隐含了，每次递增一个i时，dp当前的状态就是i-1的状态）

确定递推公式

其实没变，dp[j] = Max(dp[j],dp[j-weight[i]+value[i])，公式里没有了i，因为dp[j]在没更新的时候就是i-1的情况

初始化dp

j=0时背包容量为空。value一定是0。没有了i，j相关值都会被更新为大于0的值（价值不会为负数），所以不需要初始化了

遍历顺序

和二维一样，还是先物品，再重量，需要i，j两个参数，但是dp中i不存在

注意：和二维不一样，重量需要倒序遍历！！！

对每一个物品，先更新它在最大重量背包中的值，再逐渐降低背包容然后更新，而且背包容量小于当前物品重量的情况不需要更新了。

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

倒序更新的目的是防止相同物品被反复放入（01背包只能拿一个）
为什么正序更新会反复使用呢？因为dp[j]更新时是会用到前面的值的(用到了dp[j - weight[i]])如果正序更新，相当于在j小的时候已经拿了当前物品，在j大的时候又拿了一次（后面用到前面的值）。

比如

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

在算dp[2]的时候，相当于拿了两次0，因为此时dp[1]的值已经是拿完0后计算出的结果了。

如果倒序，没有这个问题，小的值没有更新，还是i-1时的结果。

比如：

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

最终结果位置

就是dp[bagSize]

完整代码：

public int getMax01Bag(int[] weight, int[] value, int bagWeight) {
    int wLen = weight.length;
    //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
    int[] dp = new int[bagWeight + 1];
    //遍历顺序：先遍历物品，再遍历背包容量
    for (int i = 0; i < wLen; i++) {
        for (int j = bagWeight; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[bagWeight];
}

实现细节

dp数组的大小，根据定义，i是商品的编号，所以i从0到n-1，总共n个

j是重量，j从0到bagSize，总共bagSize+1个

遍历从1开始，因为0的情况初始化过。并且j是可以等于bagSize的

判断j装不下i的情况，那这是就只能和i-1的情况相等了

当二维dp发现dp中某个维度只和之前特定的几个dp值相关（如此处i只和i-1相关）则一定是可以优化的。只存有用的就好。

推广一下，如果发现i只和i-1，i-2相关，那只存两个一维dp就行（斐波那契）

dp降维的时候一定要注意避免的情况，（本轮每个值的更新只能用上一轮更新过的值，不能用本轮更新的值）比如：本轮已经更新过dp[i]了，当i+1时如果用了dp[i]则出错了。

进阶情况

一般情况下不会直接给01背包问题，都是经过一系列转化后，问题变成了01背包问题

首先看看01背包的一大变体，不需要求最大值，而是改求是否能够凑出目标值（转换方程完全一致，从存最大值，改为存能否凑出当前目标值）

lc416 分割等和子集

等和子集其实就是看取一些元素能否凑出和为总和一半的值。典型01背包

lc1049最后一块石头的重量II

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

参考资料

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html#%E6%80%9D%E8%B7%AF

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE