背包 DP：容量限制下的选择模型

第一次碰到“背包 DP：容量限制下的选择模型”，我以为把定义和代码记下来就算学会了。真正动手时才暴露出问题：背包问题里的一维优化曾让我非常困惑，同一段循环只是容量方向不同，为什么就变成了完全不同的选择次数。这次重学我刻意放慢了速度，先看它为什么出现，再看规则怎样工作，最后才落到实现。

背包问题是动态规划里最经典的一类模型。它抽象的是：在容量或资源限制下，从一组物品里做选择，让价值最大、成本最小或方案数符合要求。

背包不只是算法题。工程里的预算分配、资源调度、组合选择、容量规划，都能看到背包思想。

背包类型地图

背包 DP 类型

图：不同背包的区别主要在“每个物品能选几次”

常见类型：

类型	物品限制	一维遍历方向
0-1 背包	每个物品最多选一次	容量倒序
完全背包	每个物品可以选无限次	容量正序
多重背包	每个物品有固定数量	二进制拆分或单调队列优化
分组背包	每组最多选一个	先枚举组

0-1 背包

状态定义：dp[i][w] 表示前 i 个物品、容量为 w 时能得到的最大价值。

转移：

不选第 i 个：dp[i-1][w]
选第 i 个：dp[i-1][w-weight[i]] + value[i]

二维写法：

int knapsack01(int[] weight, int[] value, int cap) {
    int n = weight.length;
    int[][] dp = new int[n + 1][cap + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= cap; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= weight[i - 1]) {
                dp[i][w] = Math.max(dp[i][w],
                        dp[i - 1][w - weight[i - 1]] + value[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

一维压缩：

int knapsack01Compressed(int[] weight, int[] value, int cap) {
    int[] dp = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[cap];
}

为什么倒序？因为每个物品只能选一次。倒序可以防止当前轮刚更新的 dp[w-weight] 被同一个物品再次使用。

完全背包

完全背包每个物品可以选多次，所以一维容量要正序。

int completeKnapsack(int[] weight, int[] value, int cap) {
    int[] dp = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = weight[i]; w <= cap; w++) {
            dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[cap];
}

正序意味着 dp[w-weight[i]] 可以来自当前物品本轮更新，也就是允许重复选择。

方案数问题

背包不只求最大价值，也可以求方案数。

例如硬币兑换组合数：

int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int x = coin; x <= amount; x++) {
            dp[x] += dp[x - coin];
        }
    }
    return dp[amount];
}

先枚举硬币，再枚举金额，得到的是组合数。如果顺序反过来，可能变成排列数。这是背包题里非常常见的坑。

多重背包

多重背包每个物品有数量限制。朴素做法是枚举选择几个：

dp[w] = max(dp[w], dp[w-k*weight] + k*value)

如果数量很大，可以把数量拆成 1,2,4,8... 的若干组，转成多个 0-1 物品，这叫二进制拆分。

分组背包

分组背包要求每组最多选一个。遍历顺序通常是：

枚举组
  倒序枚举容量
    枚举组内物品

它适合“多个方案互斥选择”的场景。

常见错误

0-1 背包一维压缩容量正序，导致物品被重复选。
完全背包容量倒序，导致无法重复选。
组合数和排列数循环顺序混淆。
dp[0] 初始化错误。
容量含义不清楚，是重量、金额、时间还是次数。
求最小值时忘记初始化为无穷大。

工程场景

预算有限时选择收益最大的项目组合。
服务器容量有限时选择任务部署组合。
优惠券、满减、组合套餐。
时间有限时规划学习任务。
推荐系统里控制曝光资源分配。

工程里的背包往往不止一个约束，比如预算、时间、人力、风险同时存在，这会变成多维背包或整数规划问题。

面试题

0-1 背包为什么容量要倒序？
完全背包为什么容量可以正序？
组合数和排列数的循环顺序有什么区别？
多重背包如何优化？
背包问题在工程里有哪些对应场景？

小结

背包 DP 的本质是容量约束下的选择。最关键的是搞清楚“每个物品能选几次”和“当前状态依赖上一轮还是本轮”。只要这个想清楚，0-1、完全、多重、分组背包就不会混成一锅粥。