0-1 背包问题怎么解？一维数组优化为什么内层要逆序？

直接回答：设 dp[i][w] 为只考虑前 i 件物品、容量 w 时的最大价值，转移：不选第 i 件 dp[i−1][w]，选则 dp[i−1][w−wi] + vi，取较大者。压缩成一维 dp[w] 后，内层容量循环必须从大往小（逆序）遍历——这样 dp[w−wi] 还是「上一轮」的旧值，保证每件物品只被选一次；正序会先更新小容量，同一件物品被重复选取，就变成完全背包了。

展开解析：二维到一维的关键是转移只依赖上一行且依赖的列下标严格更小，逆序滚动能原地复用数组。初始化细节：求「恰好装满」的方案存在性时 dp[0]=0 其余 −∞，求最大价值通常全 0（允许装不满）。相关家族题：完全背包（正序）、多重背包（二进制拆分转 0-1 背包）、子集和（能否凑出目标和）、分割等和子集（sum/2 的背包）、最后一块石头的重量 II（同模型）。追问方向：为什么背包 DP 是伪多项式复杂度（W 是数值不是输入长度）、回溯输出所选物品的方案。

示例：

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for cap in range(W, w - 1, -1):      # 逆序：每件只用一次
            dp[cap] = max(dp[cap], dp[cap - w] + v)
    return dp[W]