DP：01 背包

$n$ 件物品，每件有重量 $w$ 和价值 $v$，背包容量 $W$，每件只能拿或不拿，求最大价值。二维状态 $dp[i][j]$ 是前 $i$ 件、容量 $j$ 的最大价值，可以压成一维 $dp[j]$。

一维写法的关键：容量 $j$ 必须从大到小倒序枚举。

for (int i = 0; i < n; i++)
    for (int j = W; j >= w[i]; j--)      // 倒序！
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

为什么倒序？转移 $dp[j]=\max (dp[j],dp[j-w]+v)$ 要用到"上一件时"的 $dp[j-w]$。倒序时 $dp[j-w]$ 还没被这一轮更新，仍是旧值，保证每件只被拿一次。若正序，$dp[j-w]$ 已经算进了本件，等于允许同一件重复拿——那就变成了完全背包。

这也正是本节要点：正序枚举会把 01 背包错做成"每件可无限拿"的完全背包。复杂度 $O(nW)$。坑：内层循环下界写成 j >= w[i]，避免出现负下标。