背包问题：别死背模板了，看看这层「剩余空间」的逻辑

蔚蓝WEILANX2026-03-052026-03-05

背包问题：别死背模板了，看看这层「剩余空间」的逻辑

很多人刷 DP（动态规划）的时候，第一站就是背包。网上的题解一搜一大把，公式背得滚瓜烂熟，结果换个背景、换个限制条件，脑子就又空了。

其实背包问题的本质不是那几个 $i$ 和 $j$，而是你对 「剩余空间」 的调度，是你怎么在「拿」与「不拿」之间做那场贪心做不到的博弈。

今天不讲废话，直接把 01 背包和完全背包这点事儿，从底层逻辑到 Java 实现给你拆透。

这种题，一眼就是「背包」

刷题刷多了，你会发现背包题的指纹很明显。

只要题目里出现了 「资源受限」（比如负重不够了、目标和是固定的、零钱就那么多）和 「选还是不选」（拿这个物品还是那个物品），基本就跑不出背包的圈子。

01 背包：东西就一个，拿了就没了，主打一个独一无二。
完全背包：东西无限供应，只要你装得下，拿一百个也没人管，主打一个无限续杯。

01 背包：别被二维数组绕晕，它只是辅助工具

很多人初学的时候死磕 dp[i][j]，觉得这二维矩阵太抽象。其实它就是一张收益记录表。

二维的直观：状态的积累

dp[i][j] 的含义非常朴素：我在面对前 i 个物品，且背包还剩 j 容量时，我能捞到的最大价值。

核心就这一句： dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])

如果不拿第 i 个，我的价值就是上一行的同位置；如果拿了，我的价值就是「给这个物品腾空后的剩余价值」加上「这个物品本身的价值」。

// 这是最老实的写法，适合理解逻辑
public int base01Pack(int[] weight, int[] value, int bagSize) {
    int n = weight.length;
    int[][] dp = new int[n][bagSize + 1];
  
    // 初始化第一行：只看第一个物品，放得下就是它的价值
    for (int j = weight[0]; j <= bagSize; j++) dp[0][j] = value[0];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= bagSize; j++) {
            if (j < weight[i]) dp[i][j] = dp[i-1][j]; // 塞不下，只能看上一个
            else dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]);
        }
    }
    return dp[n-1][bagSize];
}

一维的优雅：为什么要倒着遍历？

等你理解了二维，你就会发现：计算 dp[i] 的时候，其实只用到了 dp[i-1]。那我们直接用一行数组滚过去不就行了？

但这里有个坑： 如果你正着更新容量，你在算 dp[j] 的时候，前面的 dp[j - weight[i]] 可能已经是这一轮更新过后的结果了——这等于你把同一个物品拿了好几次。

所以，01 背包压缩到一维时，必须倒序遍历。这是为了保证你参考的永远是「上一层」还没拿过这个物品的状态。

for (int i = 0; i < weight.length; i++) {
    for (int j = bagSize; j >= weight[i]; j--) { // 倒序是灵魂
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

完全背包：把 01 背包反过来写，就是无限选取

完全背包和 01 背包唯一的代码差别，就在那个倒序变正序。

为什么？因为完全背包就是要让前面的更新影响后面。你在计算 dp[j] 时，引用的 dp[j - weight[i]] 如果已经是这一轮更新过的，正好表示「我可以再拿一次物品 i」。

这就是为什么 正序遍历容量 = 无限选取。

for (int i = 0; i < weight.length; i++) {
    for (int j = weight[i]; j <= bagSize; j++) { // 正序实现“拿了还能拿”
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}