外观
22 - 背包问题:预算、资源与收益之间如何选择
前置阅读:21 - 动态规划的状态与转移。
本文讨论容量较小、可离散化的精确动态规划;容量巨大或约束复杂时,应进入近似算法或通用优化器选型。
摘要
假设一批任务各有固定的资源成本和收益,总容量有限,应该选择哪些任务才能让总收益最大?背包模型把任务称为“物品”,把资源成本称为“重量”,把收益称为“价值”。本文先推导每件物品最多选一次的 0-1 背包,再解释允许重复选择、要求恰好用完容量时,状态和更新规则为什么不同。
1. 0-1 背包
0-1 表示每件物品只有“选”和“不选”两种决策,最多选择一次。基本模型要求物品不可分割,重量和价值可以分别相加,且没有物品之间的依赖。设物品数为 n,总容量为 C,重量是正整数;目标是在总重量不超过 C 的条件下最大化总价值,允许一件也不选。
先用二维状态描述子问题:F[i][c] 表示只考虑前 i 件物品、总重量不超过 c 时的最大价值。这里 i 是已考虑的物品数,当前物品在数组中的下标是 i-1。
- 不选当前物品:答案沿用
F[i-1][c]。 - 选择当前物品:先为它留出重量
weight[i-1],剩余容量只能使用前i-1件物品,价值为F[i-1][c-weight[i-1]] + value[i-1]。
两种选择覆盖全部合法方案。若当前物品放得下,取两者中的较大值;否则只能不选。转移关系写成:
text
若 c < weight[i-1]:
F[i][c] = F[i-1][c]
否则:
F[i][c] = max(F[i-1][c], F[i-1][c-weight[i-1]] + value[i-1])没有物品时,任意容量都能通过空集合取得价值 0,因此 F[0][c]=0。正重量条件下,容量 0 也只能选择空集合。最终答案是 F[n][C]。
计算第 i 行只依赖第 i-1 行,所以可以用一个数组复用存储空间。每轮结束后,dp[c] 就代表这一行的最优值;但更新时必须防止旧行被提前覆盖。下面是方法片段,要求容量非负、两个数组非 null 且等长、重量为正整数,价值累加不超出 int 范围。第 4 节提供完整类。
java
static int maxValue(int capacity, int[] weight, int[] value) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.length; i++) {
for (int c = capacity; c >= weight[i]; c--) {
dp[c] = Math.max(dp[c], dp[c - weight[i]] + value[i]);
}
}
return dp[capacity];
}由于重量为正,c-weight[i] 小于 c。容量从大到小更新时,较小下标尚未被本轮覆盖,读取的仍是上一轮的值;因此选择当前物品的分支不会再次使用它。
2. 完全背包
完全背包允许每种物品选择任意次,仍要求总重量不超过容量。重量必须为正;否则零重量、正价值的物品可以无限重复,总收益就没有有限的最大值。
仍用 F[i][c] 表示只考虑前 i 种物品的最优价值。选择当前物品后,剩余容量还可以继续选择同一种物品,所以选择分支改为 F[i][c-weight[i-1]] + value[i-1]:它依赖当前行,而不是上一行。
压缩为一维时,容量因此从小到大更新。下面是核心循环片段,dp 与第 1 节一样初始化为全 0:
java
for (int i = 0; i < weight.length; i++) {
for (int c = weight[i]; c <= capacity; c++) {
dp[c] = Math.max(dp[c], dp[c - weight[i]] + value[i]);
}
}此时较小下标已经在本轮更新,dp[c - weight[i]] 可以包含当前物品,再加一次当前价值就实现了重复选择。第 4.1 节用同一组输入对比两个方向。
3. 恰好装满与不超过容量
“不超过容量”允许留出空余,因此每个容量上限都有空集合这个合法方案,初值可以是 0。“恰好装满”则要求总重量等于目标容量,必须重新定义 dp[c]:它表示总重量恰好为 c 的最大价值。
例如只有重量 2 的物品时,目标重量 3 不可能达到。若把 dp[3] 初始化为 0,就会把“没有合法组合”误写成“有一个价值为 0 的合法组合”。
因此只有 dp[0]=0,其余位置初始化为表示不可达的标记,数学上可视为负无穷。可达是指存在满足该状态条件的组合;转移前必须先检查前驱是否可达,不能把不可达标记当作真实价值相加。
第 4 节的 exact 是恰好装满的 0-1 背包,所以仍倒序更新。它用一个特殊整数作为哨兵值,即专门表示不可达的标记;无解时返回该值,调用方需识别它,而不能将它作为收益展示。
4. 完整可运行示例:0-1、完全与恰好装满
下面是仅依赖 Java 标准库的完整类,源文件名应为 KnapsackDemo.java。main 使用重量 {2,3,4}、价值 {4,5,7} 和容量 6:0-1 背包选重量 2 与 4 的物品,完全背包可选三次重量 2 的物品,恰好装满的 0-1 背包也选重量 2 与 4。按代码推导,三行预期输出依次为 11、12、11。
validate 校验非负容量、数组等长和严格正重量,但没有校验 null、数组分配上限或价值溢出。exact 使用 Integer.MIN_VALUE / 4 表示不可达;有限哨兵不能代表任意范围的负价值,使用时还需保证合法状态值高于该标记、所有加法不溢出。这些限制不会因为转移前检查可达性而自动消失。
java
import java.util.Arrays;
/**
* 可运行示例:背包问题:预算、资源与收益之间如何选择。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class KnapsackDemo {
static int zeroOne(int cap, int[] w, int[] v) {
validate(cap, w, v);
// dp[c] 表示容量不超过 c 时,已经处理过的物品能取得的最大价值。
int[] dp = new int[cap + 1];
// 容量倒序,确保当前物品在本轮最多使用一次。
for (int i = 0; i < w.length; i++) {
for (int c = cap; c >= w[i]; c--) {
// 不选物品 i 与选择物品 i 两种方案取较大值。
// 倒序保证 dp[c-w[i]] 仍来自上一轮,不含当前物品。
dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
}
}
return dp[cap];
}
static int complete(int cap, int[] w, int[] v) {
validate(cap, w, v);
int[] dp = new int[cap + 1];
// 容量正序,允许当前物品在同一轮被重复使用。
for (int i = 0; i < w.length; i++) {
for (int c = w[i]; c <= cap; c++) {
// 正序时 dp[c-w[i]] 可能已在本轮选过物品 i,因此支持重复选取。
dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
}
}
return dp[cap];
}
static int exact(int cap, int[] w, int[] v) {
validate(cap, w, v);
// 选一个远离溢出边界的哨兵值表示“该容量不可达”。
int impossible = Integer.MIN_VALUE / 4;
int[] dp = new int[cap + 1];
Arrays.fill(dp, impossible);
// 不选任何物品时,只有容量 0 恰好可达,价值为 0。
dp[0] = 0;
for (int i = 0; i < w.length; i++) {
for (int c = cap; c >= w[i]; c--) {
// 只有前驱容量可达,才能由它转移到当前容量。
if (dp[c - w[i]] != impossible) {
dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
}
}
}
return dp[cap];
}
static void validate(int cap, int[] w, int[] v) {
if (cap < 0 || w.length != v.length) {
throw new IllegalArgumentException("invalid capacity or arrays");
}
for (int weight : w) {
// 完全背包若允许重量 0 且价值为正,会产生无限收益。
if (weight <= 0) throw new IllegalArgumentException("weight must be > 0");
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
int[] w = { 2, 3, 4 },
v = { 4, 5, 7 };
System.out.println(zeroOne(6, w, v));
System.out.println(complete(6, w, v));
System.out.println(exact(6, w, v));
}
}4.1 手工推演:倒序和正序只差方向吗
只考虑一种物品,重量 2、价值 4,容量为 4,数组初始全为 0。0-1 模型只有一件可选,完全背包模型允许重复选:
- 0-1 背包倒序:先更新
dp[4]=4,再更新dp[2]=4。计算dp[4]时dp[2]还是上一轮的 0,因此物品只用一次。 - 完全背包正序:先得到
dp[2]=4,再用这个本轮新值计算dp[4]=8,表示同一物品用了两次。
遍历方向不是写法偏好,而是在控制转移读取“上一轮状态”还是“本轮状态”。
4.2 正确性不变量
不变量是算法在指定阶段始终成立的性质。对 zeroOne 和 complete,处理完前 i 个数组元素后,dp[c] 是只使用这些物品、总重量不超过 c 的最优价值;对 exact,容量含义改为“总重量恰好为 c”,无合法组合时保留不可达标记。
初值建立了各模型的边界。每轮更新把“不选”和“选”两类方案取最大值:0-1 背包选择后只读上一轮,完全背包选择后可以读本轮,恰好装满还要求前驱可达。若前驱中存在更好的合法子方案,用它替换就能提高当前方案,因此保存前驱最优值足够。逐轮保持这一性质,处理完全部物品后即可得到目标容量的答案。
4.3 复杂度、恢复方案与边界
设物品数为 n、容量为 C。三个实现最多为每件物品扫描 C+1 个状态,计入校验和初始化,时间上界为 O(n(C+1)+C+1),额外空间为 O(C+1)。容量为正且物品非空时,通常简写为时间 O(n × C)、空间 O(C);二维表则需要 O(n × C) 空间。
这称为伪多项式复杂度:循环次数取决于容量的数值,而不是表示该数值所需的位数。容量翻倍,容量循环也大致翻倍,但二进制表示可能只增加一位。因此物品少不代表计算量小;容量很大时,数组分配也可能先成为瓶颈。
这些实现只返回最优值。需要选择清单时,恢复信息会改变空间需求,见第 6 节;多资源限制如何扩大状态空间,见第 5 节。边界测试集中列在第 7 节。
5. 工程映射
预算分配、批处理组合和容量规划可以借用背包模型,前提是资源成本与收益可相加、选择规则符合模型。先确定任务是否可分割、是否可重复,再确认有哪些资源限制。
不能只根据业务中出现“容量”和“收益”就套背包:
- 任务存在前置依赖时,单个物品的选与不选不再独立,还需要用图表达“选择它必须先选择谁”的约束;
- 可以分割任务且成本、收益随份额线性变化时,更接近分数背包,即允许只选物品的一部分;其他可分割模型需按其约束考虑连续优化;
- 多种资源同时受限时,需要记录各资源的已用量或容量上限。例如同时限制 CPU 和内存,状态就要包含两个容量坐标,状态数按各维容量范围相乘;
- 需要公平性、风险或时间窗时,单一最大收益目标已经不完整。
对于非负整数价值的 0-1 背包,容量很大而价值总和较小时,可以交换状态维度:记录“达到某个总价值所需的最小重量”,再找出重量不超过容量的最大价值。这把状态规模从容量范围换成价值范围,并不适用于任意价值输入。
多维状态过大或约束更复杂时,可评估整数规划(用整数决策变量表达选择和约束的优化模型)、启发式算法(按策略寻找较好方案但通常不保证最优)或近似算法。允许近似解时,也可研究缩放价值以减少状态数的方案;具体近似保证和适用条件必须针对目标算法单独证明。
6. 方案恢复与可解释性
只保留一维 dp 通常足以得到最优值,但不足以稳定恢复选择集合。常见方案包括:
- 保留二维表。0-1 背包从
F[n][C]开始回溯:若当前值与上一行同容量的值相同,可以不选当前物品;否则选择它,扣除其重量,再退到上一行。恰好装满时需先确认目标可达,完全背包选择后则可能继续留在当前行; - 额外记录每次改进的来源,但要保存当时的前驱信息。仅记录一个可被后续更新的容量下标,可能把不同轮次的决策拼在一起;
- 对多个等价最优解规定稳定的平局处理规则(tie-break),例如价值相同时优先不选当前物品;
- 对审计型业务同时保存输入版本、目标函数和约束快照。
方案恢复不是输出层细节,它会影响内存复杂度和状态设计。
7. 验证与排障
以下是建议的验证方式,可用于检查实现的正确性:
- 小规模 0-1 背包枚举全部子集,分别按“不超过容量”和“恰好容量”筛选,再与动态规划比较。完全背包可以在严格正重量下,按每种物品最多
C / weight[i]次枚举计数作对照; - 用第 4.1 节的单物品输入检查遍历方向,区分“最多一次”和“可重复”;
- 覆盖容量 0、空数组、单物品、恰好装满无解、负价值和多个等价最优解;负价值还应检查
exact的哨兵范围限制; - 检查零/负重量是否被拒绝,并检查价值累加溢出、不可达标记误用;有选择清单时,还要核对总重量、总价值和每件物品的使用次数;
- 性能异常时分别记录物品数和容量范围,先估算状态数与转移次数,再判断是否需要换状态维度或算法。
8. 容易踩的坑
- 0-1 背包容量正序,导致重复选择同一物品。
- 完全背包倒序,错误禁止复用。
- “最多容量”和“恰好容量”初始化相同。
- 价值相加溢出。
- 只输出最大收益,业务却需要具体选择集合;需保存决策或回溯状态。
9. 总结
背包问题通过容量状态表达资源约束,遍历方向决定当前物品能否重复使用。
- 0-1 背包一维压缩时容量倒序。
- 完全背包允许复用,容量通常正序。
- 可达性初始化和答案恢复必须根据业务要求单独设计。