代码随想录算法训练营第四十一天 | 01背包理论基础、416. 分割等和子集

01背包理论基础

题目链接：https://kamacoder.com/problempage.php?pid=1046
文档讲解：01背包理论基础（一）、01背包理论基础（二）
视频讲解：01背包理论基础（一）、01背包理论基础（二）

背包问题的区别

• 01背包：每种物品只有一个
• 完全背包：每种物品有无限个
• 多重背包：每种物品有不同的个数

思路

二维dp数组

• 确定dp数组以及下标的含义：任取下标为0 - i的物品，放入容量为j的背包里，得到的最大价值为dp[i][j]。
• 确定递推公式：
  • 不放物品i，背包j的最大价值为dp[i - 1][j]；
  • 放物品i，背包j的最大价值为dp[i - 1][j - weight[i]] + i；
  • 取二者的最大值：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。
• dp数组如何初始化：第一行是背包容量为0 - j，放入物品0后的价值，那么只要背包容量大于物品0的重量，就可以初始化为物品0的价值，否则为0；第一列因为背包没有容量，所以都初始化为0
• 确定遍历顺序：对于二维数组实现01背包，先遍历背包或先遍历物品都是可以的。
• 打印dp数组，用于debug。

一维dp数组

• 确定dp数组以及下标的含义：容量为j的背包的最大价值为dp[j]。
• 确定递推公式：
  • 在二维数组中第i层的数据是由上一层得到的，所以使用滚动数组的概念，将二维压缩成一维。
  • 不放物品i，背包j的最大价值为dp[j]；
  • 放物品i，背包j的最大价值为dp[j - weight[i]] + i；
  • 取二者的最大值：dp[i][j] = Math.max(dp[j], dp[j - weight[i]] + value[i])。
• dp数组如何初始化：dp[0] = 0。
• 确定遍历顺序：先正序遍历物品，再倒序遍历背包。如果正序遍历，会将一个物品加进去多次。二维数组中数据是根据上一层得到的，两层的数据互相不影响。
• 打印dp数组，用于debug。

代码

二维dp数组

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(); // 物品
        int n = in.nextInt(); // 背包
        int[] weight = new int[m];
        int[] value = new int[m];
        int[][] dp = new int[m][n + 1];
        for (int i = 0; i < m; i++) weight[i] = in.nextInt();
        for (int i = 0; i < m; i++) value[i] = in.nextInt();
        // 初始化
        for (int i = weight[0]; i <= n; i++) dp[0][i] = value[0];
        // 遍历
        for (int i = 1; i < m; i++) {
            for (int j = 0; j <= n; j++) {
                if (weight[i] > j) 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]);
            }
        }
        System.out.println(dp[m - 1][n]);
    }
}

分析：时间复杂度：O(n²)，空间复杂度：O(n²)。

一维dp数组

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[] weights = new int[m];
        for (int i = 0; i < m; i++) weights[i] = in.nextInt();
        int[] values = new int[m];
        for (int i = 0; i < m; i++) values[i] = in.nextInt();
        int[] dp = new int[n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = n; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
        System.out.println(dp[n]);
    }
}

分析：时间复杂度：O(n²)，空间复杂度：O(n)。

416. 分割等和子集

题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/
文档讲解：https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
视频讲解：https://www.bilibili.com/video/BV1rt4y1N7jE/

思路

• 确定dp数组以及下标的含义：容量为j的背包价值为dp[j]。
• 确定递推公式：nums数组里的数就相当于物品的重量和价值，需要用target的价值装满容量为target的背包，即dp[target] = target。
• dp数组如何初始化：dp[0] = 0。
• 确定遍历顺序：先正序遍历物品，再倒序遍历背包。
• 打印dp数组，用于debug。

代码

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false;
        int[] dp = new int[sum / 2 + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum / 2; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                if (dp[j] == sum / 2) return true;
            }
        }
        return false;
    }
}

分析：时间复杂度：O(n²)，空间复杂度：O(n)。