0-1 背包问题如何用动态规划求解？一维数组为什么要倒序遍历？

简化版

0-1 背包：n 件物品，第 i 件重 w[i]、值 v[i]，背包容量 W，每件物品只能选 0 次或 1 次，求能装的最大价值。二维状态 dp[i][j] = 「前 i 件物品、容量 j 时的最大价值」，转移是「第 i 件不选 dp[i-1][j] 或选 dp[i-1][j-w[i]]+v[i]」取最大。压成一维 dp[j] 后，容量 j 必须从大到小（倒序）遍历——保证每件物品只被用一次。

详细版

二维 DP：

dp[i][j] = max(dp[i-1][j],  dp[i-1][j-w[i]] + v[i])
             └─不选第 i 件─┘  └─────选第 i 件─────┘   (需 j >= w[i])

一维滚动数组（空间 O(W)）：

int knapsack(int[] w, int[] v, int W) {
    int[] dp = new int[W + 1];       // dp[j] = 容量 j 的最大价值
    for (int i = 0; i < w.length; i++) {
        for (int j = W; j >= w[i]; j--) {          // 容量倒序！
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

状态：dp[j] = 容量为 j 时的最大价值。
转移：dp[j] = max(dp[j], dp[j-w[i]] + v[i])。
倒序遍历容量是 0-1 背包一维写法的命门——保证计算 dp[j] 时，dp[j-w[i]] 还是上一件物品（i-1） 的值，从而每件只用一次。
复杂度：O(n·W) 时间，一维 O(W) 空间。

完整版教学

一、问题：容量有限，每个物品选或不选

0-1 背包是背包问题的基础模型，几乎所有背包变体都从它衍生。「0-1」指每件物品要么整件拿走（1）、要么不拿（0），不能拆分、不能拿多件。给定容量，让总价值最大。很多看似无关的题（分割等和子集、目标和、部分和）本质都是 0-1 背包。

二、二维 DP：状态定义与转移方程

定义状态：dp[i][j] = 「只从前 i 件物品里挑、背包容量为 j 时，能装的最大价值」。

转移方程——盯住「第 i 件物品选不选」：

不选第 i 件：容量 j 全留给前 i-1 件，价值 dp[i-1][j]。
选第 i 件（前提 j >= w[i]）：先给它腾出 w[i] 的重量，剩下 j-w[i] 容量装前 i-1 件，价值 dp[i-1][j-w[i]] + v[i]。

取两者最大：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。第一行/第一列（0 件物品或容量 0）初始化为 0。答案 dp[n][W]。

三、滚动数组压成一维

注意二维转移里，dp[i][*] 只依赖上一行 dp[i-1][*]。所以可以只保留一维 dp[j]，外层每处理一件物品，就在这一维数组上原地更新——dp[j] 更新前代表「上一件时的值」，更新后代表「这一件时的值」。这样空间从 O(n·W) 压到 O(W)。但一维化带来一个致命细节：遍历容量的方向。

四、为什么一维必须倒序遍历容量（核心）

一维转移 dp[j] = max(dp[j], dp[j-w[i]] + v[i]) 里的 dp[j-w[i]]，我们希望它是「上一件物品 i-1」时的值（对应二维的 dp[i-1][j-w[i]]），这样第 i 件才只被考虑一次。

倒序遍历（j 从 W 到 w[i]）：算 dp[j] 时，j-w[i] < j，那个更小的下标这一轮还没被更新过，仍保留着上一件物品的值 —— 正确！每件物品只用一次。
正序遍历（j 从 w[i] 到 W）：算 dp[j] 时，dp[j-w[i]] 在本轮已经被更新过（包含了「这一件物品」），于是第 i 件可能被重复计入——dp[j] 用了刚加过第 i 件的 dp[j-w[i]]，相当于第 i 件被拿了多次。这就变成了完全背包（每件可无限次）。

一句话记牢：0-1 背包一维要「倒序」——倒序才能让 dp[j-w[i]] 停留在上一件的状态，保证每件只用一次；正序会让物品被重复选，那是完全背包。

五、0-1 背包 vs 完全背包的遍历差异

这是背包问题最爱考的对比，两者转移方程长得一样，唯一区别就在一维遍历方向：

	每件物品次数	一维容量遍历
0-1 背包	至多 1 次	倒序（W → w[i]）
完全背包	无限次	正序（w[i] → W）

完全背包正序，正是要利用「dp[j-w[i]] 已含本件物品」这个特性，让同一件被反复选。理解了「倒序 vs 正序如何控制物品能用几次」，两种背包就彻底通了。

六、状态语义、转移来源与遍历顺序

本题状态的完整含义是：dp[c] 表示处理完当前物品前缀后容量不超过 c 的最大价值，每件物品最多贡献一次。

转移过程是：二维为 max(dp[i-1][c], dp[i-1][c-w]+v)；压成一维后容量必须从 C 倒序到 w。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：容量 4，物品 (2,3)；若正序，更新 dp[2]=3 后同轮又令 dp[4]=6，相当于把同一物品用了两次。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

七、初始化、空间压缩与适用边界

实现边界是：恰好装满与不超过容量的初始化不同；价值可能为负时不能无脑全 0；恢复方案需记录选择信息。

核对项	本题答案
复杂度	O(nC) 时间，二维 O(nC) 或滚动 O(C) 空间
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

八、常见误区与追问

误区：一维数组正序倒序只是性能差异。 0-1 背包正序会重复使用同一物品，改变题意。
误区：所有背包 dp 都初始化 0。 恰好装满的不可达容量应为负无穷。
误区：容量越大答案一定严格增加。 只能保证不下降，可能没有合适物品改善。
追问：倒序为什么保证只用一次？ dp[c-w] 仍来自处理当前物品之前的那一层。
追问：完全背包为什么正序？ 允许读取本轮状态，代表重复选择当前物品。
追问：容量很大怎么办？ 考虑价值维 DP、Meet-in-the-middle 或近似算法。

九、加强记忆

0-1 背包：dp[i][j] = 前 i 件、容量 j 的最大价值，第 i 件选或不选——dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])。压一维 dp[j]=max(dp[j], dp[j-w[i]]+v[i]) 后容量必须倒序遍历：倒序保证 dp[j-w[i]] 还是上一件的值、每件只用一次；正序会重复选 → 变完全背包。这就是 0-1（倒序）和完全背包（正序）的唯一区别。时间 O(n·W)、空间 O(W)。

简化版

详细版