背包最优方案

一句话理解

背包最优方案：记录转移来源。

为什么要学

pre 数组或在更新时记下。

讲解

从终点倒推选了哪些物品。可能有多个最优，题目要任意还是字典序。

例子

从 W 往回看是从哪个 j-w 来的。

常见错误

• 只求到价值却忘记录。
• 倒推时物品顺序反了。