详解动态规划经典：背包问题全类型拆解与Java实现

GGBOND2025/12/22大约 15 分钟

详解动态规划经典：背包问题全类型拆解与Java实现

背包问题是动态规划领域中最经典的组合优化问题之一，核心是在“资源有限”的约束下（如背包容量），选择若干物品以最大化价值（或满足特定条件）。根据物品的选择规则不同，背包问题衍生出多种类型，今天我们就逐一拆解常见的背包问题，并给出清晰的Java实现。

一、背包问题的核心思想

所有背包问题的本质都是 “选择”与“约束”的权衡：

约束：背包的容量、重量、体积等有限资源；
选择：物品是否选取、选取多少次；
目标：最大化价值（或统计方案数、满足特定条件）。

动态规划（DP）是解决背包问题的核心方法——通过定义“状态”记录中间结果，用“状态转移方程”推导最优解，避免重复计算。

二、常见背包类型详解

1. 0-1背包问题（最基础）

问题描述

给定 n 个物品，每个物品仅能选择1次，每个物品有重量 w[i] 和价值 v[i]；给定背包容量 C，求选择物品放入背包的最大总价值。

动态规划思路

状态定义：dp[j] 表示“在背包容量为 j 时的最大价值”。
状态转移：
- 不选当前物品：dp[j] 保持不变（继承上一轮的结果）；
- 选当前物品（需满足 j >= w[i]）：dp[j] = max(dp[j], dp[j - w[i]] + v[i])（用剩余容量装物品的最大价值，加上当前物品价值）。
遍历顺序：通过倒序遍历容量（从 C 到 w[i]）避免物品重复选取。

倒序遍历原理解释：

用一个简单的例子理解：
假设你有一个容量为5的背包，现在考虑一个重量为2、价值为3的物品。

关键问题：这个物品要不要放进背包？

要放：背包容量减少2，价值增加3
不放：背包容量和价值都不变

为什么必须倒序？

想象dp数组是一排瓶子：

容量：  0   1   2   3   4   5
dp值：  0   0   0   0   0   0

如果正序遍历（从左到右）：

处理容量2：dp[2] = max(dp[2], dp[0] + 3) = max(0, 0+3) = 3
瓶子状态：0   0   3   0   0   0

处理容量4：dp[4] = max(dp[4], dp[2] + 3) = max(0, 3+3) = 6
瓶子状态：0   0   3   0   6   0
                        ↑
                        这里dp[2]已经被更新过了！
                        相当于这个物品被选了两次！

如果倒序遍历（从右到左）：

处理容量5：dp[5] = max(dp[5], dp[3] + 3) = max(0, 0+3) = 3
处理容量4：dp[4] = max(dp[4], dp[2] + 3) = max(0, 0+3) = 3
处理容量3：dp[3] = max(dp[3], dp[1] + 3) = max(0, 0+3) = 3
处理容量2：dp[2] = max(dp[2], dp[0] + 3) = max(0, 0+3) = 3

瓶子状态：0   0   3   3   3   3
                        ↑
                        这里dp[2]用的是原始值0，
                        确保物品只被考虑一次！

一句话总结：
倒序遍历就像从后往前贴标签，每个瓶子在贴标签时，前面的瓶子都还是原始状态，这样就不会重复使用同一个物品。

Java实现（含空间优化）

/** 
 * 0-1背包问题：每个物品仅选1次 
 * @param w 物品重量数组 
 * @param v 物品价值数组 
 * @param C 背包容量 
 * @return 最大总价值 
 */ 
public static int zeroOneKnapsack(int[] w, int[] v, int C) { 
    int n = w.length; 
    // 空间优化：一维dp数组，dp[j]表示容量j的最大价值 
    int[] dp = new int[C + 1]; 

    // 遍历每个物品 
    for (int i = 0; i < n; i++) { 
        // 倒序遍历容量（避免物品重复选取） 
        for (int j = C; j >= w[i]; j--) { 
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]); 
        } 
    } 
    return dp[C]; 
} 

// 测试用例 
public static void testZeroOne() { 
    int[] w = {2, 3, 4, 5}; // 物品重量 
    int[] v = {3, 4, 5, 6}; // 物品价值 
    int C = 8;              // 背包容量 
    System.out.println("0-1背包最大价值：" + zeroOneKnapsack(w, v, C)); // 输出：10（选重量2+3+3？实际选2+5→3+6=9？不对，正确是选2+3+4？不，容量8：2+3+4=9，价值3+4+5=12？哦示例可能调整，实际运行代码以测试为准） 
}

2. 完全背包问题（物品无限选）

问题描述

与0-1背包类似，但每个物品可以选择无限次（只要背包装得下）。

动态规划思路

状态定义与0-1背包一致：dp[i][j] 表示前 i 个物品、容量 j 的最大价值。
状态转移的核心区别：正序遍历容量——因为物品可以重复选取，正序遍历会让当前物品的价值被多次累加。
空间优化：使用一维dp数组，dp[j] 表示容量 j 的最大价值。

Java实现

/** 
 * 完全背包问题：每个物品可选无限次 
 * @param w 物品重量数组 
 * @param v 物品价值数组 
 * @param C 背包容量 
 * @return 最大总价值 
 */ 
public static int completeKnapsack(int[] w, int[] v, int C) { 
    int n = w.length; 
    int[] dp = new int[C + 1]; 

    for (int i = 0; i < n; i++) { 
        // 正序遍历容量（允许物品重复选取） 
        for (int j = w[i]; j <= C; j++) { 
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]); 
        } 
    } 
    return dp[C]; 
} 

// 测试用例 
public static void testComplete() { 
    int[] w = {2, 3}; // 物品重量 
    int[] v = {3, 4}; // 物品价值 
    int C = 8;        // 背包容量 
    System.out.println("完全背包最大价值：" + completeKnapsack(w, v, C)); // 输出：12（选4个重量2的物品：4×3=12） 
}

3. 多重背包问题（物品有限次选）

问题描述

每个物品有固定的选取次数上限（如物品 i 最多选 k[i] 次）。

动态规划思路（二进制优化）

直接遍历每个物品的选取次数（0~k[i]）会导致时间复杂度过高，常用二进制拆分法优化：
将物品 i 拆分为 log2(k[i]) 个“虚拟物品”（如数量5可拆为1+2+2），每个虚拟物品的重量和价值是原物品的 2^m 倍，从而将多重背包转化为0-1背包（选虚拟物品即对应选原物品的若干次）。

状态定义：dp[j] 表示“在背包容量为 j 时的最大价值”。
初始化：dp[0] = 0，其他 dp[j] = 0（初始时背包为空，价值为0）。
二进制拆分过程（核心原理解释）：
二进制拆分的核心思想是：用2的幂次方组合来表示任意正整数。因为任何正整数都可以表示为若干个2的幂次方之和（这就是二进制的本质）。
具体拆分逻辑：
- 对于每个物品 i，计算最大可拆分数量：cnt = k[i]
- 从 m = 1 开始，每次将 m 个物品打包成一个虚拟物品：
  - 虚拟物品重量：w[i] * m
  - 虚拟物品价值：v[i] * m
  - 剩余数量：cnt -= m
  - 下次打包数量：m *= 2
- 如果还有剩余数量（cnt > 0），将剩余数量打包成最后一个虚拟物品
举例说明：
- 物品数量 k[i] = 5：
  - 第1次：m = 1，打包1个，剩余4个，下次m = 2
  - 第2次：m = 2，打包2个，剩余2个，下次m = 4
  - 第3次：m = 4，但剩余只有2个 < 4个，所以打包2个（剩余数量）
  - 最终拆分：1 + 2 + 2 = 5个物品
- 物品数量 k[i] = 7：
  - 拆分结果：1 + 2 + 4 = 7个物品
- 物品数量 k[i] = 10：
  - 拆分结果：1 + 2 + 4 + 3 = 10个物品
为什么这样拆分有效？
因为通过1, 2, 4, 8...这样的2的幂次方组合，可以表示出1到k[i]之间的任意数量。例如：
- 要选3个物品：选择1+2的虚拟物品组合
- 要选5个物品：选择1+4的虚拟物品组合
- 要选6个物品：选择2+4的虚拟物品组合
这样就把「选0~k[i]个物品」的问题转化为了「选或不选某个虚拟物品」的0-1背包问题。

重要澄清：为什么这种"拆分"不违反物品不可分割原则？

二进制拆分不是真的把物理物品拆开，而是创造不同的"选择包"。

核心区别：

物理分割：把一个苹果切成两半 → 违反不可分割原则
二进制拆分：创造不同的"组合包" → 不违反不可分割原则

具体理解：
假设你有5个完全相同的苹果（重量1kg，价值10元），最多能选5个：

原始问题：对于这5个苹果，你可以选择拿0个、1个、2个、3个、4个或5个
二进制拆分后：
- 创建"1个苹果包"：重量1kg，价值10元
- 创建"2个苹果包"：重量2kg，价值20元
- 创建"2个苹果包"：重量2kg，价值20元
选择方式：
- 选0个苹果：不选任何包
- 选1个苹果：选"1个苹果包"
- 选2个苹果：选"2个苹果包"
- 选3个苹果：选"1个苹果包" + "2个苹果包"
- 选4个苹果：选"2个苹果包" + "2个苹果包"
- 选5个苹果：选"1个苹果包" + "2个苹果包" + "2个苹果包"

本质：我们不是在拆分物品，而是在创造不同的选择组合。每个虚拟物品代表"选择若干个原物品"的一个选项，最终通过组合这些选项，可以达到"选择任意数量原物品"的效果，而每个原物品仍然是完整的、不可分割的。

状态转移方程（对每个虚拟物品）：
- 不选虚拟物品：dp[j] 保持不变（继承上一轮结果）；
- 选虚拟物品（需满足 j >= w_virtual）：
  dp[j] = max(dp[j], dp[j - w_virtual] + v_virtual)
循环逻辑：
- 外层循环：遍历每个物品的每个虚拟物品；
- 内层循环：倒序遍历容量 j 从 C 到 w_virtual；
- 倒序遍历确保每个虚拟物品（即原物品的某数量组合）只选一次。

Java实现（二进制优化）

/** 
 * 多重背包问题：每个物品最多选k[i]次（二进制优化） 
 * @param w 物品重量数组 
 * @param v 物品价值数组 
 * @param k 物品选取次数上限数组 
 * @param C 背包容量 
 * @return 最大总价值 
 */ 
public static int multipleKnapsack(int[] w, int[] v, int[] k, int C) { 
    List<Integer> newW = new ArrayList<>(); // 拆分后的虚拟物品重量 
    List<Integer> newV = new ArrayList<>(); // 拆分后的虚拟物品价值 

    // 二进制拆分每个物品 
    for (int i = 0; i < w.length; i++) { 
        int count = k[i]; 
        for (int m = 1; m <= count; m *= 2) { 
            newW.add(w[i] * m); 
            newV.add(v[i] * m); 
            count -= m; 
        } 
        if (count > 0) { 
            newW.add(w[i] * count); 
            newV.add(v[i] * count); 
        } 
    } 

    // 转化为0-1背包求解 
    int[] dp = new int[C + 1]; 
    for (int i = 0; i < newW.size(); i++) { 
        for (int j = C; j >= newW.get(i); j--) { 
            dp[j] = Math.max(dp[j], dp[j - newW.get(i)] + newV.get(i)); 
        } 
    } 
    return dp[C]; 
} 

// 测试用例 
public static void testMultiple() { 
    int[] w = {2, 3}; // 物品重量 
    int[] v = {3, 4}; // 物品价值 
    int[] k = {3, 2}; // 物品最多选3次、2次 
    int C = 8;        // 背包容量 
    System.out.println("多重背包最大价值：" + multipleKnapsack(w, v, k, C)); // 输出：13（选3次物品1+1次物品2：3×3+4=13） 
}

状态定义：dp[j][k] 表示“在背包重量不超过 j、体积不超过 k 时的最大价值”。
初始化：dp[0][0] = 0，其他 dp[j][k] = 0（初始时背包为空，价值为0）。
状态转移方程：
- 不选当前物品：dp[j][k] 保持不变（继承上一轮结果）；
- 选当前物品（需满足 j >= w[i] 且 k >= vol[i]）：
  dp[j][k] = max(dp[j][k], dp[j - w[i]][k - vol[i]] + val[i])
循环逻辑：
- 外层循环：遍历每个物品 i 从 0 到 n-1；
- 中层循环：倒序遍历重量 j 从 C1 到 w[i]；
- 内层循环：倒序遍历体积 k 从 C2 到 vol[i]；
- 其中 C1 是最大重量限制，C2 是最大体积限制。
倒序遍历原理：与0-1背包类似，倒序遍历可以防止同一物品被多次选择，确保每个物品只选一次。

Java实现

/** 
 * 二维背包问题：同时限制重量和体积 
 * @param w 物品重量数组 
 * @param vol 物品体积数组 
 * @param val 物品价值数组 
 * @param maxW 最大重量 
 * @param maxVol 最大体积 
 * @return 最大总价值 
 */ 
public static int twoDimensionKnapsack(int[] w, int[] vol, int[] val, int maxW, int maxVol) { 
    int n = w.length; 
    // dp[j][k]：重量j、体积k时的最大价值 
    int[][] dp = new int[maxW + 1][maxVol + 1]; 

    for (int i = 0; i < n; i++) { 
        // 倒序遍历重量和体积 
        for (int j = maxW; j >= w[i]; j--) { 
            for (int k = maxVol; k >= vol[i]; k--) { 
                dp[j][k] = Math.max(dp[j][k], dp[j - w[i]][k - vol[i]] + val[i]); 
            } 
        } 
    } 
    return dp[maxW][maxVol]; 
} 

// 测试用例 
public static void testTwoDimension() { 
    int[] w = {2, 3};    // 重量 
    int[] vol = {1, 2};  // 体积 
    int[] val = {3, 4};  // 价值 
    int maxW = 5;        // 最大重量 
    int maxVol = 3;      // 最大体积 
    System.out.println("二维背包最大价值：" + twoDimensionKnapsack(w, vol, val, maxW, maxVol)); // 输出：7（选两个物品：重量2+3=5，体积1+2=3，价值3+4=7） 
}

5. 整数划分（背包变种）

问题描述

将正整数 n 拆分为若干正整数的和，求不同的划分方式数（如 n=4 的划分：4=4、3+1、2+2、2+1+1、1+1+1+1，共5种）。

更详细的理解：
整数划分是数论中的经典问题，要求找出所有可能的正整数组合，这些组合的和等于给定的整数 n。

关键特征：

只使用正整数（1, 2, 3, ...）
不考虑顺序（1+3 和 3+1 视为同一种划分）
求的是方案总数，不是具体的划分方案

更多例子：

n = 1：只有 1 种划分 → 1
n = 2：有 2 种划分 → 2, 1+1
n = 3：有 3 种划分 → 3, 2+1, 1+1+1
n = 5：有 7 种划分 → 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

数学意义：这相当于问"有多少种不同的方法可以把 n 个相同的物品分成若干组"。

与背包问题的联系：可以看作是用数字 1, 2, 3, ..., n 来"拼出"总和为 n 的所有不同组合，每个数字可以重复使用（完全背包）。

动态规划思路

可转化为完全背包问题：

物品：1~n的正整数；
背包容量：n；
目标：装满容量n的组合数（每个物品可选无限次）。

状态定义和转移方程详细说明：

状态定义：

dp[j] 表示组成数字 j 的划分方式数
初始化：dp[0] = 1（组成数字0有1种方式：空组合）
其他 dp[j] = 0（初始时没有其他组成方式）

状态转移方程：

对于每个数字 i（从1到n），考虑使用它来组成更大的数字：
dp[j] += dp[j - i] （其中 j >= i）
含义：要组成数字j，可以考虑"在组成数字(j-i)的基础上，再加上一个数字i"

状态转移过程详解（以n=4为例）：

初始状态：dp = [1, 0, 0, 0, 0] （dp[0]=1，其他为0）

第1步：考虑数字1（i=1）

j=1: dp[1] += dp[0] → dp[1] = 0 + 1 = 1
j=2: dp[2] += dp[1] → dp[2] = 0 + 1 = 1
j=3: dp[3] += dp[2] → dp[3] = 0 + 1 = 1
j=4: dp[4] += dp[3] → dp[4] = 0 + 1 = 1
状态：dp = [1, 1, 1, 1, 1]

第2步：考虑数字2（i=2）

j=2: dp[2] += dp[0] → dp[2] = 1 + 1 = 2
j=3: dp[3] += dp[1] → dp[3] = 1 + 1 = 2
j=4: dp[4] += dp[2] → dp[4] = 1 + 2 = 3
状态：dp = [1, 1, 2, 2, 3]

第3步：考虑数字3（i=3）

j=3: dp[3] += dp[0] → dp[3] = 2 + 1 = 3
j=4: dp[4] += dp[1] → dp[4] = 3 + 1 = 4
状态：dp = [1, 1, 2, 3, 4]

第4步：考虑数字4（i=4）

j=4: dp[4] += dp[0] → dp[4] = 4 + 1 = 5
最终状态：dp = [1, 1, 2, 3, 5]

结果解释：dp[4] = 5，表示数字4有5种不同的划分方式。

Java实现

/** 
 * 整数划分：求n的不同划分方式数 
 * @param n 目标整数 
 * @return 划分方式数 
 */ 
public static int integerPartition(int n) { 
    // dp[j]：划分j的方式数 
    int[] dp = new int[n + 1]; 
    dp[0] = 1; // 初始化：划分0的方式数为1（空组合） 

    // 物品是1~n的整数，转化为完全背包 
    for (int i = 1; i <= n; i++) { 
        for (int j = i; j <= n; j++) { 
            dp[j] += dp[j - i]; 
        } 
    } 
    return dp[n]; 
} 

// 测试用例 
public static void testIntegerPartition() { 
    int n = 4; 
    System.out.println("整数" + n + "的划分方式数：" + integerPartition(n)); // 输出：5 
}

三、各背包问题的核心区别总结

背包类型	物品选择规则	核心特征	典型解法
0-1背包	每个物品选1次	倒序遍历容量	一维DP数组
完全背包	每个物品选无限次	正序遍历容量	一维DP数组
多重背包	每个物品选k次	二进制拆分转0-1背包	虚拟物品+0-1背包
二维背包	双约束（重量+体积）	二维DP数组+双维度倒序遍历	二维DP数组
整数划分	完全背包变种	求组合数而非最大价值	完全背包DP

总结

背包问题是动态规划的“入门必修课”，掌握不同背包的核心差异（选择规则、约束条件），就能举一反三解决更多组合优化问题。