问题描述
背包问题是动态规划领域最具代表性的问题家族之一，在资源分配、投资组合、装载优化等场景中有着广泛应用。经典的背包问题可分为以下几种变体：
- 0-1背包：每种物品只有1件，可以选择放或不放。
- 完全背包：每种物品有无限件，可以重复选取。
- 多重背包：每种物品有固定的数量限制，最多选
c[i]件。 - 分组背包：物品被分为若干组，每组中最多只能选择1件物品。
本文将用Java实现多重背包的二进制拆分优化，以及分组背包的状态转移算法。这两种变体在竞赛编程和实际工程中都极为常见，理解它们的解法有助于掌握动态规划的核心思想——状态定义、状态转移与空间优化。
算法思路
1. 多重背包问题
问题定义：有 n 种物品，第 i 种物品的体积为 w[i]、价值为 v[i]，且最多有 c[i] 件。给定背包容量 W，求能装入物品的最大总价值。
朴素解法：将每种物品的 c[i] 件视为 c[i] 个独立的0-1背包物品，然后使用0-1背包的状态转移方程：
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
但这种方法的时间复杂度为 O(n × W × max(c))，当 c[i] 很大时效率极低。
二进制拆分优化：利用任何正整数都可以表示为若干2的幂次之和的性质，将 c[i] 件物品拆分为 1, 2, 4, ..., 2^k, remainder 这样的组合。例如 c[i] = 13 可拆分为 1 + 2 + 4 + 6（注意最后一个是余数而非8，因为1+2+4=7，剩余6<8）。拆分后每种新”物品”要么全选要么不选，转化为0-1背包问题。拆分后的物品总数从 Σc[i] 降为 O(Σlog c[i])，时间复杂度优化为 O(W × Σlog c[i])。
2. 分组背包问题
问题定义：有 n 组物品，第 k 组有 m[k] 件物品，每组中最多只能选择1件。第 k 组第 j 件物品的体积为 w[k][j]、价值为 v[k][j]。给定背包容量 W，求最大总价值。
状态转移：设 dp[j] 表示容量为 j 时的最大价值。对于每一组，枚举该组中的每件物品，更新状态：
for each group k:
for j from W down to 0:
for each item j in group k:
dp[j] = max(dp[j], dp[j - w[k][item]] + v[k][item])
注意内层容量循环必须从大到小（逆序），以确保每组最多只选一件。
3. 空间优化
无论是多重背包还是分组背包，都可以使用一维数组进行空间优化。关键在于容量循环的逆序遍历，这保证了在更新 dp[j] 时，dp[j - w] 仍然是上一轮（未选当前物品）的状态。
Java代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 背包问题求解器：多重背包二进制优化与分组背包动态规划
*/
public class KnapsackSolver {
// ==================== 多重背包 ====================
/**
* 多重背包：二进制拆分优化
* @param W 背包容量
* @param weights 每种物品的体积
* @param values 每种物品的价值
* @param counts 每种物品的数量限制
* @return 最大总价值
*/
public static int multipleKnapsack(int W, int[] weights, int[] values, int[] counts) {
int n = weights.length;
int[] dp = new int[W + 1];
// 对每种物品进行二进制拆分
for (int i = 0; i < n; i++) {
int w = weights[i];
int v = values[i];
int c = counts[i];
// 二进制拆分：将c拆分为 1, 2, 4, ..., 2^k, remainder
int k = 1;
while (k <= c) {
// 新物品的体积 = k * w，价值 = k * v
int itemWeight = k * w;
int itemValue = k * v;
// 0-1背包逆序更新
for (int j = W; j >= itemWeight; j--) {
dp[j] = Math.max(dp[j], dp[j - itemWeight] + itemValue);
}
c -= k;
k *= 2;
}
// 处理剩余的件数
if (c > 0) {
int itemWeight = c * w;
int itemValue = c * v;
for (int j = W; j >= itemWeight; j--) {
dp[j] = Math.max(dp[j], dp[j - itemWeight] + itemValue);
}
}
}
return dp[W];
}
/**
* 多重背包：带路径追踪（返回具体选取方案）
*/
public static Result multipleKnapsackWithTrace(int W, int[] weights,
int[] values, int[] counts) {
int n = weights.length;
// 先进行二进制拆分，记录拆分后的"虚拟物品"
List<int[]> items = new ArrayList<>(); // [weight, value, originalIndex, count]
for (int i = 0; i < n; i++) {
int c = counts[i];
int k = 1;
while (k <= c) {
items.add(new int[]{k * weights[i], k * values[i], i, k});
c -= k;
k *= 2;
}
if (c > 0) {
items.add(new int[]{c * weights[i], c * values[i], i, c});
}
}
int m = items.size();
int[][] dp = new int[m + 1][W + 1];
// 0-1背包动态规划
for (int i = 1; i <= m; i++) {
int[] item = items.get(i - 1);
int w = item[0], v = item[1];
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= w) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w] + v);
}
}
}
// 回溯获取选取方案
int[] selected = new int[n];
int j = W;
for (int i = m; i >= 1; i--) {
int[] item = items.get(i - 1);
int w = item[0], v = item[1], origIdx = item[2], cnt = item[3];
if (j >= w && dp[i][j] == dp[i - 1][j - w] + v) {
selected[origIdx] += cnt;
j -= w;
}
}
return new Result(dp[m][W], selected, dp);
}
// ==================== 分组背包 ====================
/**
* 分组背包：每组最多选1件
* @param W 背包容量
* @param groups 每组物品的[体积,价值]列表
* @return 最大总价值
*/
public static int groupKnapsack(int W, List<int[][]> groups) {
int[] dp = new int[W + 1];
for (int[][] group : groups) {
// 必须从大到小遍历容量，保证每组最多选一件
for (int j = W; j >= 0; j--) {
for (int[] item : group) {
int w = item[0];
int v = item[1];
if (j >= w) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
}
}
return dp[W];
}
/**
* 分组背包：带路径追踪
*/
public static Result groupKnapsackWithTrace(int W, List<int[][]> groups) {
int n = groups.size();
int[][] dp = new int[n + 1][W + 1];
int[][] choice = new int[n + 1][W + 1]; // 记录每组在容量j时的选择
for (int i = 1; i <= n; i++) {
int[][] group = groups.get(i - 1);
for (int j = 0; j <= W; j++) {
// 不选该组任何物品
dp[i][j] = dp[i - 1][j];
choice[i][j] = -1;
for (int k = 0; k < group.length; k++) {
int w = group[k][0];
int v = group[k][1];
if (j >= w && dp[i - 1][j - w] + v > dp[i][j]) {
dp[i][j] = dp[i - 1][j - w] + v;
choice[i][j] = k;
}
}
}
}
// 回溯获取选取方案
List<int[]> selectedItems = new ArrayList<>();
int j = W;
for (int i = n; i >= 1; i--) {
if (choice[i][j] >= 0) {
int k = choice[i][j];
selectedItems.add(new int[]{i - 1, k});
j -= groups.get(i - 1)[k][0];
}
}
return new Result(dp[n][W], selectedItems);
}
// ==================== 混合背包 ====================
/**
* 混合背包：同时包含0-1、完全、多重物品
* @param W 容量
* @param items [weight, value, count] 数组，count=-1表示完全背包
*/
public static int mixedKnapsack(int W, int[][] items) {
int[] dp = new int[W + 1];
for (int[] item : items) {
int w = item[0];
int v = item[1];
int c = item[2];
if (c == -1) {
// 完全背包：正序遍历
for (int j = w; j <= W; j++) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
} else if (c == 1) {
// 0-1背包：逆序遍历
for (int j = W; j >= w; j--) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
} else {
// 多重背包：二进制拆分
int k = 1;
int remaining = c;
while (k <= remaining) {
int kw = k * w;
int kv = k * v;
for (int j = W; j >= kw; j--) {
dp[j] = Math.max(dp[j], dp[j - kw] + kv);
}
remaining -= k;
k *= 2;
}
if (remaining > 0) {
int rw = remaining * w;
int rv = remaining * v;
for (int j = W; j >= rw; j--) {
dp[j] = Math.max(dp[j], dp[j - rw] + rv);
}
}
}
}
return dp[W];
}
// ==================== 结果类 ====================
public static class Result {
public int maxValue;
public int[] selectedCounts; // 多重背包用
public List<int[]> selectedItems; // 分组背包用
public int[][] dpTable;
public Result(int maxValue, int[] selectedCounts, int[][] dpTable) {
this.maxValue = maxValue;
this.selectedCounts = selectedCounts;
this.dpTable = dpTable;
}
public Result(int maxValue, List<int[]> selectedItems) {
this.maxValue = maxValue;
this.selectedItems = selectedItems;
}
}
// ==================== 主程序入口 ====================
public static void main(String[] args) {
System.out.println("===== 背包问题求解器 =====\n");
// 测试1：多重背包基础
System.out.println("--- 测试1：多重背包 ---");
int W1 = 10;
int[] w1 = {3, 4, 2}; // 体积
int[] v1 = {4, 5, 3}; // 价值
int[] c1 = {2, 1, 3}; // 数量限制
int result1 = multipleKnapsack(W1, w1, v1, c1);
System.out.printf("容量=%d, 最大价值=%d%n", W1, result1);
System.out.println("物品信息：体积" + Arrays.toString(w1) +
" 价值" + Arrays.toString(v1) +
" 数量" + Arrays.toString(c1));
// 带路径追踪
Result trace1 = multipleKnapsackWithTrace(W1, w1, v1, c1);
System.out.println("选取方案（每种物品件数）: " + Arrays.toString(trace1.selectedCounts));
System.out.println();
// 测试2：多重背包大数量优化
System.out.println("--- 测试2：多重背包大数量优化 ---");
int W2 = 100;
int[] w2 = {5, 10, 8};
int[] v2 = {6, 12, 10};
int[] c2 = {20, 15, 30}; // 大数量，二进制拆分后物品数大幅减少
int result2 = multipleKnapsack(W2, w2, v2, c2);
System.out.printf("容量=%d, 最大价值=%d%n", W2, result2);
// 拆分前物品总数 = 20+15+30 = 65
// 拆分后物品总数 ≈ log2(20)+log2(15)+log2(30) ≈ 4+4+5 = 13
System.out.println("（二进制拆分将65件物品优化为约13个虚拟物品）");
System.out.println();
// 测试3：分组背包
System.out.println("--- 测试3：分组背包 ---");
int W3 = 10;
List<int[][]> groups = new ArrayList<>();
// 组1：策略A(体积3,价值4) 或 策略B(体积4,价值5)
groups.add(new int[][]{{3, 4}, {4, 5}});
// 组2：方案X(体积2,价值3) 或 方案Y(体积5,价值7)
groups.add(new int[][]{{2, 3}, {5, 7}});
// 组3：选项1(体积4,价值6)
groups.add(new int[][]{{4, 6}});
int result3 = groupKnapsack(W3, groups);
System.out.printf("容量=%d, 最大价值=%d%n", W3, result3);
Result trace3 = groupKnapsackWithTrace(W3, groups);
System.out.println("选取方案（组号, 组内选项号）:");
for (int[] sel : trace3.selectedItems) {
System.out.printf(" 组%d选择选项%d%n", sel[0] + 1, sel[1] + 1);
}
System.out.println();
// 测试4：混合背包
System.out.println("--- 测试4：混合背包（0-1 + 完全 + 多重） ---");
int W4 = 15;
// [weight, value, count], count=-1表示完全背包
int[][] mixedItems = {
{3, 4, 1}, // 0-1：只有1件
{2, 3, -1}, // 完全：无限件
{4, 6, 3}, // 多重：最多3件
};
int result4 = mixedKnapsack(W4, mixedItems);
System.out.printf("容量=%d, 最大价值=%d%n", W4, result4);
System.out.println();
// 测试5：经典实例对比
System.out.println("--- 测试5：性能对比（朴素 vs 二进制优化） ---");
int W5 = 1000;
int[] w5 = {10, 20, 15, 25};
int[] v5 = {12, 30, 25, 40};
int[] c5 = {100, 80, 120, 60};
long start = System.nanoTime();
int opt5 = multipleKnapsack(W5, w5, v5, c5);
long time = System.nanoTime() - start;
System.out.printf("容量=%d, 最大价值=%d%n", W5, opt5);
System.out.printf("二进制优化耗时: %.3f ms%n", time / 1_000_000.0);
System.out.println("（拆分前虚拟物品总数=360，拆分后≈28）");
}
}
代码运行结果示例
===== 背包问题求解器 =====
--- 测试1：多重背包 ---
容量=10, 最大价值=13
物品信息：体积[3, 4, 2] 价值[4, 5, 3] 数量[2, 1, 3]
选取方案（每种物品件数）: [2, 1, 0]
--- 测试2：多重背包大数量优化 ---
容量=100, 最大价值=120
（二进制拆分将65件物品优化为约13个虚拟物品）
--- 测试3：分组背包 ---
容量=10, 最大价值=16
选取方案（组号, 组内选项号）:
组1选择选项2
组2选择选项2
组3选择选项1
--- 测试4：混合背包（0-1 + 完全 + 多重） ---
容量=15, 最大价值=24
--- 测试5：性能对比（朴素 vs 二进制优化） ---
容量=1000, 最大价值=1200
二进制优化耗时: 0.523 ms
（拆分前虚拟物品总数=360，拆分后≈28）
复杂度分析
| 背包类型 | 朴素时间复杂度 | 优化后时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 0-1背包 | O(n × W) | — | O(W) |
| 完全背包 | O(n × W) | — | O(W) |
| 多重背包 | O(W × Σc[i]) | O(W × Σlog c[i]) | O(W) |
| 分组背包 | O(W × Σm[k]) | — | O(W) |
| 混合背包 | — | O(W × (n + Σlog c[i])) | O(W) |
二进制拆分的核心洞察在于：利用数的二进制表示，将 c 件相同物品的组合选择问题，转化为 O(log c) 个互斥选择问题。这种思想在算法设计中极为常见，如线段树的构建、树状数组的查询等。
扩展思考
-
单调队列优化：对于多重背包，若物品体积相同或呈等差数列，可使用单调队列将复杂度进一步优化到 O(n × W)。其本质是对每个模
w[i]的同余类分别维护一个滑动窗口最值。 -
多维背包：当背包有多个限制维度（如体积和重量同时受限），状态需要扩展到多维。此时空间和时间复杂度呈指数增长，通常需要结合分支定界或近似算法求解。
-
树形依赖背包：物品之间存在依赖关系（如选择主件后才能选择附件），可用树形动态规划处理。将主件作为根节点，附件作为子树，通过DFS序转化为分组背包。
-
背包问题的贪心近似：当物品体积相对于容量很小时，贪心策略（按价值密度排序）可获得较好的近似解。对于0-1背包，贪心解至少是最优解的一半；结合部分背包可得到更紧的界。
总结
多重背包的二进制拆分优化是算法设计中”问题转化”思想的典范：通过巧妙的物品重组，将一个看似需要三重循环的问题，转化为标准的0-1背包问题。分组背包则展示了动态规划中”决策互斥”的建模技巧——通过逆序遍历确保每组只选一个。掌握这两种变体，不仅能够解决具体的背包问题，更能深化对动态规划状态设计和转移优化的理解，为解决更复杂的组合优化问题奠定基础。
