动态规划3：01背包问题

引言

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

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

问题描述

01背包的基本定义

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

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

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

约束条件：

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

经典例题

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

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

示例 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]，我们有两种选择：

不选择第 i 个数字：dp[i][j] = dp[i-1][j]
选择第 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，不可能达到

详细用例分析

为了更好地理解01背包问题，我们通过一个具体例子来详细分析整个求解过程。

经典背包用例

问题设定：

背包容量：W = 8
物品信息：

物品编号	重量(weight)	价值(value)
1	2	3
2	3	4
3	4	5
4	5	6

目标：在背包容量为8的限制下，选择物品使总价值最大。

状态转移过程详解

我们使用二维DP表 dp[i][w] 来记录前i个物品在容量为w时的最大价值。

初始化DP表

       容量 0  1  2  3  4  5  6  7  8
物品0     0  0  0  0  0  0  0  0  0
物品1     0  
物品2     0  
物品3     0  
物品4     0

第1个物品（重量=2，价值=3）

对于每个容量w，我们考虑：

不选择物品1：dp[1][w] = dp[0][w] = 0
选择物品1：需要 w >= 2，此时 dp[1][w] = dp[0][w-2] + 3

逐个计算：

w=0,1: 容量不够，不能选择 → dp[1][0]=0, dp[1][1]=0
w=2: max(不选:0, 选:0+3) = 3 → dp[1][2]=3
w=3: max(不选:0, 选:0+3) = 3 → dp[1][3]=3
…以此类推

       容量 0  1  2  3  4  5  6  7  8
物品0     0  0  0  0  0  0  0  0  0
物品1     0  0  3  3  3  3  3  3  3
物品2     0  
物品3     0  
物品4     0

第2个物品（重量=3，价值=4）

对于每个容量w：

不选择物品2：dp[2][w] = dp[1][w]
选择物品2：需要 w >= 3，此时 dp[2][w] = dp[1][w-3] + 4

关键计算：

w=0,1,2: 容量不够选择物品2 → 保持原值
w=3: max(不选:3, 选:dp[1][0]+4=0+4=4) = 4
w=4: max(不选:3, 选:dp[1][1]+4=0+4=4) = 4
w=5: max(不选:3, 选:dp[1][2]+4=3+4=7) = 7 ✨
w=6: max(不选:3, 选:dp[1][3]+4=3+4=7) = 7
w=7: max(不选:3, 选:dp[1][4]+4=3+4=7) = 7
w=8: max(不选:3, 选:dp[1][5]+4=3+4=7) = 7

       容量 0  1  2  3  4  5  6  7  8
物品0     0  0  0  0  0  0  0  0  0
物品1     0  0  3  3  3  3  3  3  3
物品2     0  0  3  4  4  7  7  7  7
物品3     0  
物品4     0

第3个物品（重量=4，价值=5）

继续填充第3行，重点关注几个关键位置：

w=6: max(不选:7, 选:dp[2][2]+5=3+5=8) = 8
w=7: max(不选:7, 选:dp[2][3]+5=4+5=9) = 9 ✨
w=8: max(不选:7, 选:dp[2][4]+5=4+5=9) = 9

       容量 0  1  2  3  4  5  6  7  8
物品0     0  0  0  0  0  0  0  0  0
物品1     0  0  3  3  3  3  3  3  3
物品2     0  0  3  4  4  7  7  7  7
物品3     0  0  3  4  5  7  8  9  9
物品4     0

第4个物品（重量=5，价值=6）

最后一行的计算：

w=7: max(不选:9, 选:dp[3][2]+6=3+6=9) = 9
w=8: max(不选:9, 选:dp[3][3]+6=4+6=10) = 10 ✨

最终DP表：

       容量 0  1  2  3  4  5  6  7  8
物品0     0  0  0  0  0  0  0  0  0
物品1     0  0  3  3  3  3  3  3  3
物品2     0  0  3  4  4  7  7  7  7
物品3     0  0  3  4  5  7  8  9  9
物品4     0  0  3  4  5  7  8  9  10

最优解分析

从 dp[4][8] = 10，我们知道最大价值是10。那么具体选择了哪些物品呢？

回溯求解：

dp[4][8] = 10 ≠ dp[3][8] = 9 → 选择了物品4
容量变为 8-5=3，查看 dp[3][3] = 4
dp[3][3] = 4 ≠ dp[2][3] = 4 → 相等，说明没选择物品3
查看 dp[2][3] = 4 ≠ dp[1][3] = 3 → 选择了物品2
容量变为 3-3=0，结束

最优选择：物品2（重量3，价值4）+ 物品4（重量5，价值6）

总重量：3 + 5 = 8 ≤ 8 ✓
总价值：4 + 6 = 10 ✓

分割等和子集用例详解

现在让我们通过一个具体例子来理解如何将分割等和子集问题转化为01背包问题。

问题：判断数组 [1, 5, 11, 5] 能否分割成两个元素和相等的子集。

转化过程：

计算总和：sum = 1 + 5 + 11 + 5 = 22
判断奇偶性：22是偶数，可能存在解
目标和：target = 22 ÷ 2 = 11
问题转化：能否从数组中选择一些数字，使它们的和等于11？

这就变成了一个01背包问题：背包容量为11，物品重量和价值都是数字本身。

DP表构建过程：

       目标和 0  1  2  3  4  5  6  7  8  9  10 11
数字0        T  F  F  F  F  F  F  F  F  F  F  F
数字1(1)     T  T  F  F  F  F  F  F  F  F  F  F
数字2(5)     T  T  F  F  F  T  T  F  F  F  F  F
数字3(11)    T  T  F  F  F  T  T  F  F  F  F  T
数字4(5)     T  T  F  F  F  T  T  F  F  F  T  T

详细填充过程：

处理数字1（值为1）：

j=0: dp[1][0] = dp[0][0] = T
j=1: dp[1][1] = dp[0][1] || dp[0][0] = F || T = T ✨
j=2到11: 都等于dp[0][j] = F

处理数字5：

j=5: dp[2][5] = dp[1][5] || dp[1][0] = F || T = T ✨
j=6: dp[2][6] = dp[1][6] || dp[1][1] = F || T = T ✨
其他位置保持原值

处理数字11：

j=11: dp[3][11] = dp[2][11] || dp[2][0] = F || T = T ✨

处理数字5（第二个）：

j=10: dp[4][10] = dp[3][10] || dp[3][5] = F || T = T ✨
j=11: dp[4][11] = dp[3][11] || dp[3][6] = T || T = T

结果：dp[4][11] = T，说明可以找到和为11的子集。

具体解：通过回溯可以找到子集 [1, 5, 5]（和为11）和子集 [11]（和为11）。

用例代码实现

让我们用代码来验证上面的分析：

public class KnapsackExample {
    public static void main(String[] args) {
        // 经典背包问题用例
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 8;
        System.out.println("经典01背包最大价值: " + knapsack(weights, values, capacity));
        
        // 分割等和子集用例
        int[] nums = {1, 5, 11, 5};
        System.out.println("能否分割等和子集: " + canPartition(nums));
    }
    
    // 经典01背包实现
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        // 填充DP表
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                // 不选择第i个物品
                dp[i][w] = dp[i-1][w];
                
                // 选择第i个物品（如果可以的话）
                if (w >= weights[i-1]) {
                    dp[i][w] = Math.max(dp[i][w], 
                                       dp[i-1][w-weights[i-1]] + values[i-1]);
                }
            }
        }
        
        // 打印DP表（用于理解）
        System.out.println("DP表:");
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                System.out.printf("%2d ", dp[i][w]);
            }
            System.out.println();
        }
        
        return dp[n][capacity];
    }
    
    // 分割等和子集实现
    public static 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;
        
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
            
            // 打印每轮状态（用于理解）
            System.out.print("处理数字 " + num + " 后: ");
            for (int k = 0; k <= target; k++) {
                System.out.print(dp[k] ? "T " : "F ");
            }
            System.out.println();
        }
        
        return dp[target];
    }
}

运行结果：

DP表:
 0  0  0  0  0  0  0  0  0 
 0  0  3  3  3  3  3  3  3 
 0  0  3  4  4  7  7  7  7 
 0  0  3  4  5  7  8  9  9 
 0  0  3  4  5  7  8  9 10 
经典01背包最大价值: 10

处理数字 1 后: T T F F F F F F F F F F 
处理数字 5 后: T T F F F T T F F F F F 
处理数字 11 后: T T F F F T T F F F F T 
处理数字 5 后: T T F F F T T F F F T T 
能否分割等和子集: true

通过这个完整的用例分析，我们可以清楚地看到：

状态转移的具体过程：每一步如何从前一状态推导出当前状态
DP表的填充规律：理解为什么某些位置的值会发生变化
两类问题的本质联系：经典背包求最大价值，分割子集判断可达性
算法优化的实际效果：从二维数组到一维数组的空间优化

代码实现

二维DP解法

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解法

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];
}

为什么要从后往前遍历？

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

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

优化后的复杂度

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

解题步骤总结

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

问题识别：判断是否为01背包问题
- 有容量/重量限制
- 每个物品只能选择一次
- 求最大价值/是否可达某个值
状态定义：dp[i][j] 表示前i个物品在容量为j时的最优解
状态转移：考虑第i个物品选择或不选择
边界处理：初始化第0行和第0列
空间优化：使用一维数组，逆序遍历

总结

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

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

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