二维动态规划＞＞01背包问题与普遍应用_二维背包

0、内容梗概

        在二维动态规划中，01背包问题是动态规划中的经典问题。

•  本文首先学习、总结01背包问题的思路、方法与实现。
•  之后，01背包问题与其说是问题，更可以是一种解题思路，或者说套路。

        如果遇到别的题目时，能够清楚地判断出它是一个01背包的类似问题，就可以套用01背包问题的模板，来进行解题。例如416. 分割等和子集 - 力扣（Leetcode）

本文内容即： 
        (1)01背包是什么 
        (2)如何用01背包思想解答其他题目（416. 分割等和子集 - 力扣（Leetcode））

---

1、01背包

1.1 介绍01背包问题

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

        解释：就是在有限的最大重量w里，选任意个具有重量和价值的商品（每个商品就1个），求能得到的最大价值。

1.2 解题思路

（1）分析

对于动态规划类型的题目，我们知道：

1. 需要将大问题拆解为多个小问题来解决
2. 通过求出所有小问题的答案，放入dp数组，递推到大问题。

        这个题目作为二维动态规划，是因为有2个动态变化的变量：最大背包重量，和，到底从前几？个物品里选。        
        （至于为什么要这么思考，不需要知道，因为我们要学习01背包的模式，来套其他的题目，因此这就是一个模板）

        因此，可以构建二维dp数组dp[i][j] ：
        表示从下标为[0-i]的物品里任意取，放进重量为j的背包，价值总和最大的值。

（2）确定递推公式⭐

        要求二维dp[i][j]的递推公式，其实就是求出dp所有子问题组成全集的方法：
        思路是：先看能不能、再看要不要。

        对于任意 dp[i][j]，其意义是最大重量为j的约束下，从0~i这些商品任选，能够得到的最大价值。动态规划的奥秘在于，不要去思考具体是怎么选、怎么组合得到的最大价值，而是仅仅通过“递推”的思想完成整个任务。
        对于dp[i][j]而言，是从0~i里来选的，那么0~i里来选，有可能选了第i个，也有可能没选。
        我们首先要考虑：能不能选第i个？
        如果第i个的重量weight[i]比整个背包的最大承重j都要大，那么就算从0~i里选，实际上也肯定不能选第i个。因此，dp[i][j]其实等效于从0~i-1里选，最大容量为j的这个状态。
        即：dp[i][j] = dp[i-1][j]
        其次，我们要考虑：能选，但是要不要选？
        如果现在能选第i个商品了，即第i个商品有资格被选（重量小于等于总重），就要考虑要不要选：
        如果不要选上第i个，就仍然是等效于从0~i-1里选，最大容量为j。dp[i][j] = dp[i-1][j]
        如果要选上第i个，那么dp[i][j]这个最大价值该等于什么呢？既然选了第i个，至少就有第i个的价值Value[i]，然后背包的最大容量只剩下j-weight[i]了，然后从0~i-1里接着选。
        因此，为dp[i - 1][j - weight[i]] + value[i]
        而dp[i][j]为最大价值，因此要取两种情况的Max。
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

（3）初始化数组
 

        初始化数组要考虑数组的意义。
        首先，在j为0这一列，最大重量都为0了，你怎么组合也甭想装进去啊。因此dp[i][0]全为0
        其次，i为0这一行 ，相当于从0~0的物品里任选（其实就是只选物品0），背包重量为j的约束下，能取得的最大价值。因为物品就1个，只能用一次，因此，在j>=weight[i]的列，都应该为Value[i].

（4）代码实现     

package LeetcodeLearn.Algorithm.sort;
 
import java.util.Arrays;
 
/**
 * @Author ZhangQihao
 */
public class package0_1 {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }
    /**
     * 动态规划获得结果
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(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数组:i是物品标号
        // j是：容量为j的背包
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                //能不能？
                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]);
                    //前为不要，后为要。
                }
            }
        }
 
 
        // 打印dp数组
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}

---

2、01背包问题的模板套用 

2.1 如何套用01背包模板

        如何把01背包问题套用到其他问题上，以416. 分割等和子集 - 力扣（Leetcode）为例子进行说明。

        题目：给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例：     

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

        能否分成两个等和数组，其实可以变换为：选任意多个数字的和，为所有数字总和 / 2。
        如果像下面这样考虑，这个问题就类似01背包问题了。

        相当于：坐标是商品标号，数值是商品的重量，要往一个背包里装，背包的最大重量为所有数值和/2。
        即：从下标0~i选取其中任意的数字，是否存在一种方案，使其和为j
        即：推出每一个状态，直到i为数组末位，j为和的二分之一，输出dp。

         到这里就很清晰了，其余分析类似上文，也可看代码注释。

2.2 代码实现及解释

class Solution {
    public boolean canPartition(int[] nums) {
    //从下标0~i选取其中任意的数字，是否存在一种方案，使其和为j
    //如果能够构建这个问题的状态方程，那么推导到i=nums.length-1、j=数组和/2的时候
    //dp数组的值就是最终的答案了。
        int n = nums.length;
        //长度为1，不可分
        if(n == 1){
            return false;
        }
        //和为奇数，不可平分
        int sum = 0,MaxNum = 0;
        for(int num : nums){
            sum += num;
            MaxNum = Math.max(MaxNum,num);
        }
        if(sum % 2 == 1){
            return false;
        } 
        //如果数组中的最大值，大于了和的1/2，不可平分
        int target = sum / 2;
        if(MaxNum > target){
            return false;
        }
        
        //构建动态dp
        boolean[][] dp = new boolean[n][target + 1];//画图即可
        //初始化：
        for(int i = 0; i < n; i++){
            dp[i][0] = true;//从0~i索引，选取一种方案能否组成和为0的集合：当然可以，一个数字也不选，这种方案可行
        }
        dp[0][nums[0]] = true;
        for(int i = 1; i < n; i++){
            for(int j = 1; j < target + 1; j++){
                //先判断能不能选
                if(nums[i] > j){
                    //不能选
                    dp[i][j] = dp[i - 1][j];
                }else{
                    //能选，需要考虑要不要选
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[n - 1][target];
    }
}

3、总结

        还有非01状态的背包问题等相关多维动态规划问题，以后熟练了再继续写。