数据结构与算法 / 系统课时
背包问题
背包问题
零一背包要在容量有限时选择若干物品,使总价值最大,并且每件物品最多使用一次。本课先用二维状态解释选择关系,再压缩为一维数组,重点说明容量倒序遍历如何防止同一物品被重复计算。
学习目标
- 定义“前 i 件物品、容量 c”的零一背包状态
- 推导选择或不选择当前物品的转移方程
- 使用容量倒序遍历完成一维空间优化
零一背包的状态与选择
设第 i 件物品重量为 weight[i]、价值为 value[i],背包容量为 C。零一背包中的“零一”表示每件物品只能不选或选一次,目标是在总重量不超过容量时获得最大价值。
二维状态可定义为 dp[i][c]:只考虑前 i 件物品、容量为 c 时的最大价值。不选第 i 件物品时沿用 dp[i - 1][c];容量足够时,选择它的候选值是 dp[i - 1][c - weight[i - 1]] + value[i - 1]。两种选择取较大值。
一维压缩为何必须倒序
当前行只依赖上一行,因此可以删除物品维度,把转移写成 dp[c] = max(dp[c], dp[c - weight] + value)。关键是容量必须从大到小遍历,确保读取的 dp[c - weight] 仍是处理当前物品之前的旧状态。
若容量从小到大遍历,较小容量刚更新出的结果会在同一轮再次参与计算,相当于重复选择当前物品,模型就从零一背包变成了完全背包。

主示例:一维零一背包
下面的 Java 17 程序校验数组长度、重量和容量,然后使用外层遍历物品、内层倒序遍历容量的方式求解。返回完整状态数组,便于验证各容量对应的最大价值。
import java.util.Arrays;
public class KnapsackDemo {
public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 8, 8};
int capacity = 6;
int[] dp = solveZeroOneKnapsack(weights, values, capacity);
System.out.println("最大价值: " + dp[capacity]);
System.out.println("状态数组: " + Arrays.toString(dp));
}
private static int[] solveZeroOneKnapsack(
int[] weights,
int[] values,
int capacity
) {
if (weights == null || values == null) {
throw new IllegalArgumentException("重量和价值数组不能为 null");
}
if (weights.length != values.length || capacity < 0) {
throw new IllegalArgumentException("数组长度不一致或容量非法");
}
int[] dp = new int[capacity + 1];
for (int item = 0; item < weights.length; item++) {
if (weights[item] <= 0) {
throw new IllegalArgumentException("物品重量必须为正数");
}
for (int currentCapacity = capacity;
currentCapacity >= weights[item];
currentCapacity--) {
dp[currentCapacity] = Math.max(
dp[currentCapacity],
dp[currentCapacity - weights[item]] + values[item]
);
}
}
return dp;
}
}预期输出:
最大价值: 11
状态数组: [0, 0, 3, 4, 8, 8, 11]容量为 6 时,选择重量 2、价值 3 的物品和重量 4、价值 8 的物品,总重量为 6,总价值为 11。
边界、复杂度与模型区别
标准零一背包允许不装满,因此 dp 初始值为 0,表示可以什么都不选。若题目要求恰好装满,默认值 0 会把不可达容量误判为可达,需要使用明确的不可达标记并单独初始化 dp[0]。
设物品数为 n、容量为 C,时间复杂度为 O(nC),一维空间复杂度为 O(C)。这里的复杂度依赖容量数值大小,因此属于伪多项式复杂度。需要恢复具体物品时,保留二维表最直接;一维实现则要额外记录决策来源。