01 背包

一句话理解

01 背包：每件物品最多用一次。

为什么要学

背包第一模型。

讲解

f[j]=max(f[j], f[j-w]+v)，容量从大到小。

例子

for (int i = 1; i <= n; i++)
  for (int j = W; j >= w[i]; j--)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

倒序避免同一件用两次。

常见错误

• 正序变成完全背包。
• 体积 0 死循环。