第九章 动态规划part03

详细布置

01背包问题 二维

文章讲解

例子
物品为：

问背包能背的物品最大价值是多少？
这个问题的暴力解法：每个物品只有两个状态：取和不取，用回溯算法枚举。

动规五部曲

1. 确定dp数组以及下标的含义
   对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

   
   
   image.png

2. 确定递推公式
   可以有两个方向推出来dp[i][j]，

   • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，就是回到i-1一行，所以此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
   • 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
   • 所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp数组如何初始化
   首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

   • dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
   • 那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
     当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

image.png

• 从递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。

• 但只不过一开始就统一把dp数组统一初始为0，更方便一些。

4. 确定遍历顺序：先遍历物品和先遍历背包重量都可以，只是先遍历物品更好理解

5. 举例推导dp数组

   
   
   image.png

import java.util.Scanner;

public class Knapsack {
    static int n, bagweight; // bagweight代表行李箱空间

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            n = scanner.nextInt();
            bagweight = scanner.nextInt();
            solve(scanner);
        }
        scanner.close();
    }

    private static void solve(Scanner scanner) {
        int[] weight = new int[n]; // 存储每件物品所占空间
        int[] value = new int[n];  // 存储每件物品价值
        for (int i = 0; i < n; ++i) {
            weight[i] = scanner.nextInt();
        }
        for (int j = 0; j < n; ++j) {
            value[j] = scanner.nextInt();
        }

        // dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
        int[][] dp = new int[n][bagweight + 1];

        // 初始化, 因为需要用到dp[i - 1]的值
        // j < weight[0]已在上方被初始化为0
        // j >= weight[0]的值就初始化为value[0]
        for (int j = weight[0]; j <= bagweight; j++) {
            dp[0][j] = value[0];
        }

        for (int i = 1; i < n; i++) { // 遍历科研物品
            for (int j = 0; j <= bagweight; j++) { // 遍历行李箱容量
                // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                }
                // 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值
                // 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 + 该物品的价值构成
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
        System.out.println(dp[n - 1][bagweight]);
    }
}

01背包问题 一维

文章讲解

思路
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

动规五部曲

1. 确定dp数组的定义
   在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2. 一维dp数组的递推公式

• dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
• dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）
• 此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，
• 所以递归公式为：
  dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 一维dp数组如何初始化

• dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
• 递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

4. 一维dp数组遍历顺序

• 一维dp遍历的时候，背包是从大到小: 倒序遍历是为了保证物品i只被放入一次，否则物品0就会被重复加入多次。

 //遍历顺序：先遍历物品，再遍历背包容量
        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]);
            }
        }

5. 举例推导dp数组

   
   
   image.png

import java.util.Scanner;

public class KnapsackOneDimensionalDP {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取 M 和 N
        int M = scanner.nextInt();
        int N = scanner.nextInt();

        int[] costs = new int[M];
        int[] values = new int[M];

        for (int i = 0; i < M; i++) {
            costs[i] = scanner.nextInt();
        }
        for (int j = 0; j < M; j++) {
            values[j] = scanner.nextInt();
        }

        // 创建一个动态规划数组dp，初始值为0
        int[] dp = new int[N + 1];

        // 外层循环遍历每个类型的研究材料
        for (int i = 0; i < M; ++i) {
            // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
            for (int j = N; j >= costs[i]; --j) {
                // 考虑当前研究材料选择和不选择的情况，选择最大值
                dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i]);
            }
        }

        // 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值
        System.out.println(dp[N]);

        scanner.close();
    }
}

416. 分割等和子集

本题是 01背包的应用类题目
文章讲解

思路

• 为什么能抽象成背包问题：有目标值且只能取一次，符合01背包。
• 集合中出现sum/2的子集总和，就是可以分割成两个相同元素和子集了。
• 套用01背包问题：
  • 背包的体积为sum / 2
  • 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
  • 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。

动规五部曲

1. 确定dp数组以及下标的含义
   dp[j]表示：背包容量为j，所背物品的的最大价值为dp[j];
2. 确定递推公式
   01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
   本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
   所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3. dp数组如何初始化
   从dp[j]的定义来看，首先dp[0]一定是0。
   如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。
   这样才能让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖了。
   本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。
4. 确定遍历顺序
   和01背包 一维数组一样

5. 举例推导dp数组
   如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j。
   物品的重量和物品的价值是一样的，所选物品的重量只能小于等于背包重量，因此所选物品的价值也只能小于等于背包的重量，所以求的是所选物品价值的最大值，当物品价值的最大值等于背包重量时，其实也就表示所选物品的重量等于背包价值，也就是找到了子集和等于目标值。

   
   
   image.png

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < n; i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            //剪枝一下，每完成内层循环就判断一下
            if(dp[target] == target)
                return true;
        }
        return dp[target] == target;
    }
}