算法刷题系列（五十）：背包 DP——在容量约束下做选择

算法刷题系列（五十）：背包 DP——在容量约束下做选择

背包问题把“选哪些物品”与“总容量不能超限”放在一起。物品有重量（或体积）和价值，目标通常是在容量内最大化价值。0/1 背包中每件物品最多选一次；完全背包中每种物品可以重复选。两者状态相似，原地更新时的循环方向却相反。

一、二维状态与转移

令 dp[i][c] 表示只考虑前 i 件物品、容量上限为 c 时的最大价值。第 i 件物品重量 w、价值 v：

• 不选它：沿用 dp[i - 1][c]；
• 若 c >= w，选它：dp[i - 1][c - w] + v。

因此 0/1 背包转移为：

dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w] + v)

二维写法很好理解，压缩到一维后，更新时读写同一数组，必须通过遍历方向保证右侧来源仍代表“上一件物品之前”。

二、为什么 0/1 与完全背包方向相反

0/1 背包：容量从大到小

for c 从 capacity 向下到 w:
    dp[c] = max(dp[c], dp[c - w] + value)

从大到小更新时，dp[c - w] 尚未被当前物品改写，故当前物品不会重复进入同一方案。

完全背包：容量从小到大

for c 从 w 到 capacity:
    dp[c] = max(dp[c], dp[c - w] + value)

从小到大时，较小容量状态可能已经使用过当前物品。将它扩展到更大容量，正是允许重复选取的含义。

三、例子：容量 7 的 0/1 背包

三件物品为 (重量, 价值) = (2, 3), (3, 4), (4, 5)，容量为 7。可以选前两件，重量 5、价值 7；也可以选第二、三件，重量 7、价值 9。最优值为 9。

如果错误地在 0/1 背包中正向遍历，处理第一件物品时会把 dp[2] 更新为 3，随后用这个新值更新 dp[4] = 6，等于把同一件物品选了两次。这恰好把 0/1 问题误写成了可重复选取。

四、Java 实现：两种背包价值最大化

本实现要求重量为正、价值非负。容量可以为 0；零重量物品会被拒绝，避免完全背包出现无限重复的歧义。

public class KnapsackDp {
    private static void validate(int[] weights, int[] values, int capacity) {
        if (weights == null || values == null || weights.length != values.length) {
            throw new IllegalArgumentException("weights and values must have equal length");
        }
        if (capacity < 0) {
            throw new IllegalArgumentException("capacity must be non-negative");
        }
        for (int i = 0; i < weights.length; i++) {
            if (weights[i] <= 0 || values[i] < 0) {
                throw new IllegalArgumentException("weights must be positive and values non-negative");
            }
        }
    }

    public static long zeroOne(int[] weights, int[] values, int capacity) {
        validate(weights, values, capacity);
        long[] dp = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            for (int c = capacity; c >= weights[i]; c--) {
                dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }

    public static long complete(int[] weights, int[] values, int capacity) {
        validate(weights, values, capacity);
        long[] dp = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            for (int c = weights[i]; c <= capacity; c++) {
                dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4};
        int[] values = {3, 4, 5};
        if (zeroOne(weights, values, 7) != 9
                || complete(weights, values, 7) != 10
                || zeroOne(weights, values, 0) != 0) {
            throw new AssertionError("knapsack test failed");
        }
    }
}

完全背包样例答案为 10：重量 2 的物品可选两件，重量 3 的物品可选一件，总重量 7、总价值 10。

五、Python 实现

def _validate(weights, values, capacity):
    if weights is None or values is None or len(weights) != len(values):
        raise ValueError("weights and values must have equal length")
    if capacity < 0:
        raise ValueError("capacity must be non-negative")
    if any(weight <= 0 for weight in weights):
        raise ValueError("weights must be positive")
    if any(value < 0 for value in values):
        raise ValueError("values must be non-negative")

def zero_one_knapsack(weights, values, capacity):
    _validate(weights, values, capacity)
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for current in range(capacity, weight - 1, -1):
            dp[current] = max(dp[current], dp[current - weight] + value)
    return dp[capacity]

def complete_knapsack(weights, values, capacity):
    _validate(weights, values, capacity)
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for current in range(weight, capacity + 1):
            dp[current] = max(dp[current], dp[current - weight] + value)
    return dp[capacity]

assert zero_one_knapsack([2, 3, 4], [3, 4, 5], 7) == 9
assert complete_knapsack([2, 3, 4], [3, 4, 5], 7) == 10
assert zero_one_knapsack([], [], 0) == 0

六、状态含义、正确性与复杂度

逐件处理物品。处理第 i 件前，dp[c] 是此前物品在容量 c 内的最优值；每次更新只在“不选”和“选当前件”之间取较大值。0/1 使用逆序遍历保证来源没有包含当前件，完全背包正序遍历则有意允许来源已经包含当前件。每件物品的所有容量都被考虑，因此归纳可得最终状态覆盖所有合法选择。

时间复杂度为 O(nC)，滚动数组空间为 O(C)，其中 n 是物品数，C 是容量上限。价值用 Java long，以降低累计价值溢出风险。

七、边界与常见错误

1. 循环方向抄反：先判断物品能否重复，再决定容量方向。
2. 用“恰好装满”的状态套“容量不超过”：当前实现初始全零，表示容量上限约束；恰好装满时通常要用不可达标记初始化其他状态。
3. 忽略零重量物品：完全背包若零重量且正价值，答案无界；应按题意处理或拒绝输入。
4. 误以为容量单位总是小：O(nC) 在 C 很大时并不适用，需考虑其他算法或状态压缩方式。
5. 忘记负价值的语义：本实现允许不选任何物品，因而限定价值非负以保持接口清晰；若题目要求必须选择，应重新定义初始状态。

小结

背包 DP 的状态描述已处理物品与可用容量。二维转移区分“选或不选”；压缩成一维后，0/1 背包逆序，完全背包正序。循环方向并非语法细节，而是状态转移是否会重复使用当前物品的保证。