数据结构与算法 / 系统课时

背包问题

背包问题

零一背包要在容量有限时选择若干物品,使总价值最大,并且每件物品最多使用一次。本课先用二维状态解释选择关系,再压缩为一维数组,重点说明容量倒序遍历如何防止同一物品被重复计算。

学习目标

  • 定义“前 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 程序校验数组长度、重量和容量,然后使用外层遍历物品、内层倒序遍历容量的方式求解。返回完整状态数组,便于验证各容量对应的最大价值。

java
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;
    }
}

预期输出:

text
最大价值: 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)。这里的复杂度依赖容量数值大小,因此属于伪多项式复杂度。需要恢复具体物品时,保留二维表最直接;一维实现则要额外记录决策来源。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

背包问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通