解题报告-论对“分组背包”的新理解

分组背包都知道，但是有一种新式分组背包，它不像我们想的那样每组只能选一个，但是这样的背包问题又是与分组强相关的，那么怎么做呢？

这道题、这道题和这道题就是这种分组背包的典范。这种背包问题的共同特征是：选完一组背包中的上一个后，才能选下一个。

乍一看，这是一个依赖背包问题，因为它们之间存在依赖关系，“选完上一个才能选下一个”。但是，如果用依赖背包去做，时间复杂度是 \(O(nV^2)\) 的，很不可接受，那么这种题有什么异于依赖背包的特殊性质吗？

首先，如果我们把依赖关系树建出来，会发现每一组物品都表现为一条链的形式，这就意味着我们不用考虑给每个子树分配多少空间。其次，既然是分组背包，我们在一组中是只能选一个物品的，而在这条链当中，这表现为你只能选前 \(i\) 个物品。

这使我们受到启发，这不就是前缀和吗？将每一组中每一个物品按照依赖关系排序后，将每一个物品 \(i\) 的价值 \(v_i\) 设为 \(\sum_{j\le i}v_j\)，重量 \(w_i\) 设为 \(\sum_{j\le i} w_j\)。这样既满足了依赖关系，又满足了分组背包“每组背包只能选一个”的限制。

当然了，在一些具有某些特殊性质的此类分组背包问题中，我们甚至可以直接把每组背包的每个物品全部拆开，普通背包处理。这样的分组背包要满足 \(\forall i<j,w_i-w_{i-1}\ge w_j-w_{j-1}\)。这样差分地把每一个 \(w_i\) 设为 \(w_i-w_{i-1}\) 即可。但是这个性质太强，所以不经常用。