引言

在前面的文章中，我们学习了动态规划入门和最长公共子序列问题。今天我们将探讨动态规划中最为经典和重要的问题之一——01背包问题。

01背包问题是动态规划的核心问题，它不仅在算法面试中频繁出现，更是理解动态规划思想的绝佳案例。掌握了01背包，你就掌握了一把解决众多动态规划问题的钥匙。

问题描述

01背包的基本定义

有一个容量为 W 的背包和 n 个物品，每个物品有两个属性：

  • 重量 weight[i]：第 i 个物品的重量
  • 价值 value[i]：第 i 个物品的价值

目标：在不超过背包容量的前提下，选择若干物品装入背包，使得背包中物品的总价值最大。

约束条件：

  • 每个物品只能选择一次（0 或 1），这就是 “01” 的含义
  • 所选物品的总重量不能超过背包容量

经典例题

例题：LeetCode 416. 分割等和子集

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

1
2
3
4
5
6
7
8
9
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

虽然这道题看起来与背包问题不同，但本质上是一个01背包的变形问题。

解题思路

1. 问题转化

对于分割等和子集问题，我们可以这样思考：

  • 如果数组总和为 sum，要分割成两个相等子集，那么每个子集的和应该是 sum/2
  • 问题转化为：能否从数组中选择一些数字，使它们的和等于 sum/2
  • 这就是一个标准的01背包问题！

2. 状态定义

定义状态 dp[i][j] 表示：前 i 个数字中，能否选出一些数字使得它们的和等于 j。

  • i 表示考虑前 i 个数字（范围：0 到 n）
  • j 表示目标和（范围：0 到 sum/2）
  • dp[i][j] 为布尔值，true 表示可以达到，false 表示不能达到

3. 状态转移方程

对于第 i 个数字 nums[i-1]，我们有两种选择：

  1. 不选择第 i 个数字：dp[i][j] = dp[i-1][j]
  2. 选择第 i 个数字（前提是 j >= nums[i-1]）：dp[i][j] = dp[i-1][j-nums[i-1]]

综合两种情况：

1
dp[i][j] = dp[i-1][j] || (j >= nums[i-1] && dp[i-1][j-nums[i-1]])

4. 边界条件

  • dp[0][0] = true：前0个数字，目标和为0，肯定可以达到（什么都不选）
  • dp[0][j] = false（j > 0）：前0个数字，目标和大于0，不可能达到

代码实现

二维DP解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public boolean canPartition(int[] nums) {
    int n = nums.length;
    int sum = 0;
    
    // 计算数组总和
    for (int num : nums) {
        sum += num;
    }
    
    // 如果总和为奇数，无法分割成两个相等子集
    if (sum % 2 != 0) {
        return false;
    }
    
    int target = sum / 2;
    
    // dp[i][j] 表示前i个数字能否组成和为j
    boolean[][] dp = new boolean[n + 1][target + 1];
    
    // 边界条件：前0个数字，目标和为0，可以达到
    dp[0][0] = true;
    
    // 填充DP表
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= target; j++) {
            // 不选择第i个数字
            dp[i][j] = dp[i-1][j];
            
            // 选择第i个数字（如果可以选择的话）
            if (j >= nums[i-1]) {
                dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
            }
        }
    }
    
    return dp[n][target];
}

复杂度分析

  • 时间复杂度：O(n × sum)，其中 n 是数组长度，sum 是数组元素之和
  • 空间复杂度：O(n × sum)

空间优化

观察状态转移方程，我们发现 dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]，也就是只依赖于上一行的状态。

因此我们可以使用滚动数组优化空间复杂度。

一维DP解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    
    if (sum % 2 != 0) {
        return false;
    }
    
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;  // 目标和为0，总是可以达到
    
    for (int num : nums) {
        // 从后往前遍历，避免重复使用同一个数字
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}

为什么要从后往前遍历？

这是空间优化的关键点！我们来分析一下：

  1. 正向遍历的问题：如果从前往后遍历，dp[j] 可能会使用到已经更新过的 dp[j-num]，这相当于同一个数字被使用了多次
  2. 逆向遍历的优势：从后往前遍历，dp[j-num] 还是上一轮的值，保证了每个数字只被使用一次

优化后的复杂度

  • 时间复杂度：O(n × sum)
  • 空间复杂度：O(sum) ✨

解题步骤总结

解决01背包问题的标准步骤：

  1. 问题识别：判断是否为01背包问题

    • 有容量/重量限制
    • 每个物品只能选择一次
    • 求最大价值/是否可达某个值

  2. 状态定义：dp[i][j] 表示前i个物品在容量为j时的最优解

  3. 状态转移：考虑第i个物品选择或不选择

  4. 边界处理：初始化第0行和第0列

  5. 空间优化：使用一维数组，逆序遍历

相关题目

掌握了01背包的核心思想后，你可以尝试以下相关题目：

总结

01背包问题是动态规划的核心问题，它体现了动态规划的精髓：

  1. 状态定义清晰：明确每个状态的含义
  2. 转移方程简洁：选择或不选择，逻辑清晰
  3. 优化思路明确：空间换时间的滚动数组技巧

通过01背包问题，我们不仅学会了一种解题方法，更重要的是掌握了动态规划的思维模式。在后续的学习中，这种思维方式将帮助我们解决更多复杂的问题。

系列文章

推荐练习

  • 在LeetCode上练习更多背包相关题目
  • 尝试理解多重背包、完全背包等变形问题
  • 思考01背包在实际项目中的应用场景