背包DP之多重背包

背包DP之多重背包

• • 一、多重背包基础认知
  • • 1.1 问题定义
    • 1.2 核心特征
  • 二、基础解法：暴力拆分
  • • 2.1 核心思路
    • 2.2 代码实现
    • 2.3 局限性分析
  • 三、优化解法：二进制拆分
  • • 3.1 优化原理
    • 3.2 拆分步骤
    • 3.3 代码实现
    • 3.4 复杂度分析
  • 四、二进制拆分过程
  • 五、多重背包的变种与应用
  • • 5.1 变种问题
    • 5.2 应用场景
    • 三种背包的区别
    • 总结

背包问题模型中多重背包是介于0/1背包（每种物品1个）和完全背包（每种物品无限个）之间的中间态——它允许每种物品选择有限次（如每种物品最多选3个），这种模型更贴近现实场景（如“商品限购”“物资有限”），但解法复杂度更高。

一、多重背包基础认知

1.1 问题定义

给定n种物品，每种物品有重量w[i]、价值v[i]和数量上限cnt[i]；背包容量为C。每种物品最多选择cnt[i]次，求在总重量不超过C的前提下，能装入物品的最大总价值。

示例：

• 输入：n=2, C=10, w=[3,4], v=[5,6], cnt=[2,2]（物品0最多2个，物品1最多2个）
• 输出：17（选择2个物品0（3×2=6重量，5×2=10价值）和1个物品1（4重量，6价值），总重量6+4=10，总价值10+6=16？最优应为2个物品1（4×2=8重量，6×2=12）+1个物品0（3重量，5）→ 总重量11>10；正确最优：2个物品0（6重量，10）+1个物品1（4重量，6）→ 总重量10，价值16？或1个物品0（3）+2个物品1（8）→ 总重量11>10，因此正确输出16）

1.2 核心特征

• 数量限制：每种物品有明确的选择上限（cnt[i]），区别于0/1背包（cnt[i]=1）和完全背包（cnt[i]=+∞）。
• 容量约束：总重量≤C，与其他背包模型一致。
• 优化目标：在数量和容量双重约束下最大化总价值。

多重背包的本质是“带数量和容量双重约束的物品选择优化”，其基础解法可通过0/1背包扩展得到，但直接实现效率较低，需通过“二进制拆分”优化。

二、基础解法：暴力拆分

2.1 核心思路

多重背包可直接转化为0/1背包：将每种物品按数量上限cnt[i]拆分为cnt[i]个独立物品（每个物品只能选1次），然后用0/1背包的解法求解。

例如：物品0（w=3, v=5, cnt=2）可拆分为2个相同物品：(3,5)和(3,5)，后续按0/1背包处理（每个物品最多选1次）。

2.2 代码实现

public class MultipleKnapsack { /** * 多重背包基础实现（暴力拆分） * @param n 物品种类数 * @param C 背包容量 * @param w 重量数组 * @param v 价值数组 * @param cnt 数量上限数组 * @return 最大价值 */ public int maxValue(int n, int C, int[] w, int[] v, int[] cnt) { // 步骤1：暴力拆分物品（转化为0/1背包物品列表） List<Integer> newW = new ArrayList<>(); List<Integer> newV = new ArrayList<>(); for (int i = 0; i < n; i++) { // 将第i种物品拆分为cnt[i]个 for (int k = 0; k < cnt[i]; k++) { newW.add(w[i]); newV.add(v[i]); } } // 步骤2：用0/1背包求解 int[] dp = new int[C + 1]; for (int i = 0; i < newW.size(); i++) { int currW = newW.get(i); int currV = newV.get(i); // 0/1背包逆序遍历 for (int j = C; j >= currW; j--) { dp[j] = Math.max(dp[j], dp[j - currW] + currV); } } return dp[C]; } public static void main(String[] args) { MultipleKnapsack solver = new MultipleKnapsack(); int n = 2; int C = 10; int[] w = {3, 4}; int[] v = {5, 6}; int[] cnt = {2, 2}; System.out.println(solver.maxValue(n, C, w, v, cnt)); // 输出16 }}

2.3 局限性分析

• 时间复杂度：设物品总数量为N = sum(cnt[i])，则复杂度为O(N×C)。当cnt[i]较大（如cnt[i]=1000）时，N可达10^6，C=10^4时总操作次数为10^10，严重超时。
• 空间复杂度：拆分后物品列表需存储N个物品，内存占用大。

因此，暴力拆分仅适用于cnt[i]较小的场景（如cnt[i]≤10），需更高效的优化方法。

三、优化解法：二进制拆分

3.1 优化原理

二进制拆分的核心是“用少量物品组合表示所有可能的选择次数”，避免暴力拆分的冗余。

例如：cnt=5（最多选5个），可拆分为1、2、2（1+2+2=5）：

• 选0个：不选任何拆分物品；
• 选1个：选1；
• 选2个：选2；
• 选3个：选1+2；
• 选4个：选2+2；
• 选5个：选1+2+2。

通过2^0, 2^1, ..., 2^k, r（r为剩余数量）的拆分方式，可覆盖0~cnt的所有选择次数，且拆分后物品数从cnt降至log2(cnt)（如cnt=1000仅需10个拆分物品）。

3.2 拆分步骤

对每种物品i（数量cnt[i]）：

1. 初始化k=1（从2^0开始）；
2. 若k ≤ cnt[i]，则拆分出一个重量k×w[i]、价值k×v[i]的物品，cnt[i] -= k，k *= 2；
3. 若cnt[i] > 0，则拆分出一个重量cnt[i]×w[i]、价值cnt[i]×v[i]的物品；
4. 拆分后的物品按0/1背包处理（每个拆分物品最多选1次）。

3.3 代码实现

public class MultipleKnapsackOptimized { /** * 多重背包优化实现（二进制拆分） * @param n 物品种类数 * @param C 背包容量 * @param w 重量数组 * @param v 价值数组 * @param cnt 数量上限数组 * @return 最大价值 */ public int maxValue(int n, int C, int[] w, int[] v, int[] cnt) { // 步骤1：二进制拆分物品 List<Integer> newW = new ArrayList<>(); List<Integer> newV = new ArrayList<>(); for (int i = 0; i < n; i++) { int currW = w[i]; int currV = v[i]; int currCnt = cnt[i]; // 二进制拆分：k=1,2,4,... for (int k = 1; k <= currCnt; k *= 2) { newW.add(k * currW); newV.add(k * currV); currCnt -= k; } // 剩余数量拆分 if (currCnt > 0) { newW.add(currCnt * currW); newV.add(currCnt * currV); } } // 步骤2：0/1背包求解 int[] dp = new int[C + 1]; for (int i = 0; i < newW.size(); i++) { int currW = newW.get(i); int currV = newV.get(i); for (int j = C; j >= currW; j--) { dp[j] = Math.max(dp[j], dp[j - currW] + currV); } } return dp[C]; } public static void main(String[] args) { MultipleKnapsackOptimized solver = new MultipleKnapsackOptimized(); int n = 2; int C = 10; int[] w = {3, 4}; int[] v = {5, 6}; int[] cnt = {2, 2}; System.out.println(solver.maxValue(n, C, w, v, cnt)); // 输出16 }}

3.4 复杂度分析

• 时间复杂度：拆分后物品总数N\' = sum(log2(cnt[i]))，若cnt[i]≤1000，n=100，则N\'≈100×10=1000，C=10^4时总操作次数为1000×10^4=10^7，效率大幅提升。
• 空间复杂度：O(N\' + C)，N\'远小于暴力拆分的N。

二进制拆分是多重背包的标准优化方法，适用于cnt[i]较大的场景（cnt[i]≤10^5均可处理）。

四、二进制拆分过程

以示例中“物品0（w=3, v=5, cnt=2）”为例：

1. 拆分cnt=2：
   • k=1：1 ≤ 2，拆分出(1×3, 1×5)=(3,5)，currCnt=2-1=1；
   • k=2：2 > 1，停止循环；
   • 剩余currCnt=1，拆分出(1×3, 1×5)=(3,5)；
   • 拆分后物品：[(3,5), (3,5)]（与暴力拆分相同，因cnt较小）。

以“物品（cnt=5）”为例：

1. 拆分cnt=5：
   • k=1：拆分(1w, 1v)，currCnt=5-1=4；
   • k=2：拆分(2w, 2v)，currCnt=4-2=2；
   • k=4：4 > 2，停止循环；
   • 剩余currCnt=2：拆分(2w, 2v)；
   • 拆分后物品：(1w,1v), (2w,2v), (2w,2v)（3个物品，覆盖0~5所有选择）。

五、多重背包的变种与应用

5.1 变种问题

1. 混合背包（0/1+完全+多重）：

   • 问题：物品可能是0/1（cnt=1）、完全（cnt=+∞）或多重（1<cnt<+∞）。
   • 解法：分类处理——0/1直接加、完全按正序、多重二进制拆分后按0/1处理。

2. 二维多重背包（重量+体积约束）：

   • 问题：物品有重量和体积两个约束，需同时满足。
   • 解法：用二维DP数组dp[j][k]（j为重量，k为体积），拆分后按二维0/1背包处理。

3. 数量下限约束：

   • 问题：每种物品至少选minCnt[i]个，最多选maxCnt[i]个。
   • 解法：先强制选minCnt[i]个（扣除容量和价值），剩余数量按maxCnt[i]-minCnt[i]的多重背包处理。

5.2 应用场景

• 商品限购：如“每人最多买3件”，用多重背包选择最优组合。
• 物资分配：如“仓库有5台设备，每台重量10，价值20”，有限运力下最大化运输价值。
• 资源打包：如“零件按包出售（每包2个），最多买4包”，转化为多重背包（cnt=4，每包视为拆分后的物品）。

三种背包的区别

总结

多重背包的核心是“数量限制下的物品选择”，其解法的关键是通过“二进制拆分”将问题高效转化为0/1背包，避免暴力拆分的冗余：

1. 基础解法：暴力拆分为0/1背包，仅适用于cnt[i]较小的场景。
2. 优化解法：二进制拆分通过2^k组合覆盖所有选择次数，将复杂度从O(N×C)降至O(sum(log cnt[i])×C)。
3. 变种迁移：混合背包、二维约束等变种可通过分类处理和维度扩展解决。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～