分层DP

显然直接 $01$ 背包会超时并且超空间 套路：分层 $DP$ 「考虑将每个子结构看作一层（也就是包含了不止 $1$ 个物品的信息），并且大层不会对小层造成影响，可以考虑先进行每一层的自我更新（即用当前层物品更新当前层答案），再进行层的合并，此时考虑低层对高层的影响」 正题 那么这题有一个特殊性质： $V_i = a \times 2^b$ b值大的物品不会影响零碎剩余的重量上限。 将物品按b值分阶段处理。 那么就是分层 $DP$ 先通过普通的 $01$ 背包更新当前层自身最优解 再进行层合并： 令 $g_{i, j}​$ 表示第 $i​$ 层，$a​$ 为 $j​$ 的最优解，$f_{i, j}​$ 表示第 $i​$ 层，$a​$ 为 $j​$，并且再加上 $V_{total}​$ 的 $1…i - 1​$ 位的最优解 那么对于第 $i$ 层，枚举当前 $j$ 对于转移，枚举在自身层内消耗的空间 $(j - k) \times 2^i$，那么还剩下 $k \times 2^i + V_{total}\{1…i - 1\}$ 的空间，分配给上一层，那么可得转移方程为 （注：$w_i ...