knapsack 题解

▶

INFO 题面

有 个物品，每个物品可以用二元组 表示，代表物品的体积、单价。

有若干个大小为 的背包，每个背包能装下任意多个体积和不超过 的物品，此外使用一个背包还需要花费代价，代价是此背包内所有物品单价的最大值。

现在，你需要将这 个物品放入任意多个背包中，使得所有背包的代价和最小，另外你需要输出有多少种方案。

两种方案不同定义为存在两个物品 ，满足 和 在一个方案中被装在了同一个背包中，而另一个方案不在同一个背包中。

方案数对 取模。

对于所有数据，满足 ，，。

感觉是不是不止一次见到过这个题目了。在洛谷网校看到了一次，在云斗看到了一次。感觉是一个很有趣的题目。

做法

最小值

首先我们考虑如何算出最小值。

见到这个数据范围基本可以想到状压 DP（面向数据范围编程）。有一个较为朴素的暴力。

考虑 表示已经将 集合中分为了若干组之后最小的代价。转移的时候枚举子集，判断重量和是否小于 直接转移即可。时间复杂度 。其实这道题部分 OJ 上的数据比较水，这个方法加上一些剪枝可能就过了。我手造了一个简单的 Hack（ 个的重量和代价都是 的物品）卡掉了一些。

通常来说想要优化掉枚举子集有一个常见的技巧，记录最后一组的信息，考虑一次加入一个元素对于答案的影响。此时最后一组的信息包括最大值和子集和，此外你还需要记录代价。但是你发现这个结果并不是很好定义一个偏序关系，因此你只能考虑把一些信息放到状态里。比如说用 在集合 中最后一组的最大值为 ，重量和为 的最小代价。此时算法复杂度变成了 ，仍然不足以通过。此时尝试缩减状态数之类的，比如钦定从大到小加入元素，但是你仍然要记录上一个加入的元素是什么，其实缩减不了空间。

接下来说说这个神奇的正解。考虑折半搜索，先分成前后两半搜索，计算出不存在一组跨过中间的情况的最优解。接下来考虑跨过中间的最优解，令 表示左侧选择了集合 和 的最小代价。由于分组的代价只和最大价值有关，因此考虑将数组按照价值排序，这样代价只和右半部分有关了。因此，我们考虑分步，先处理右半部分的转移。

具体地，我们定义两个数组 和 ，前者存放 值，后者存放所有 对，满足第一步只转移右半部分时（左半部分不变），可以转移到 的方案。之后再枚举 的一个超集，求出其重量。那么一个合法的转移要求就是 。此时对左右两侧分别做一个双指针即可。

算法的流程如下：

• 对于每个 ，预处理集合的重量和和代价（价值的最大值），将集合的和记作 ，代价记作 。即 。
• 枚举 。
  • 枚举 ，向 中加入 。
  • 枚举 ，记录 。
  • 将记录下来的 对和 （请注意，不是 ）排序，双指针转移到 。注意需要考虑右半边不选的情况，此时代价就是左边的最大值。

注意到两个枚举子集和的时间复杂度都是 ，需要枚举 次，因此总复杂度就是 乘上一个排序的复杂度。但是，这个仍然不足以通过这道题。

注意到对于每个集合，它的子集和超集以及差集的重量是确定的，我们只需要提前把顺序预处理出来即可。

计数

我们注意到这个转移方法虽然可以求出最小值，但是直接计数会导致很多重复情况。考虑什么时候会重复计算，容易发现一个方案的分组会以不同的顺序加入导致重复计算。此时我们只需要钦定每个集合的转移顺序即可。比如，我们钦定最后一个加入集合的数必须要包含集合中编号最小的元素，这样每个方案的分组加入集合的顺序就是确定的（编号最小的元素从大到小）。

实现细节

在考虑跨过中间的情况，如果形如 可以直接从之前右半部分的搜索复制过来，而形如 则会从 转移过来。

附件

knapsack.zip