soft O(W) 做价值为 1 的背包

· · 算法·理论

来源是 WC xtq 的课件。今天面刺了 xtq，解决了数个月前我的问题。虽然我已经不知道当时想的是什么、以及为什么我不会这一部分了。

有问题请指出。

背包大小是 W，每个数有重量 \le W。

首先是一个很神秘的结构观察：

设有 n 种物品，第 i 种物品选了 a_i 个，称这个方案的重量是其中物品的重量之和。

那么对于某个重量，考察其最优解中 a 字典序最大的（若存在）。

可以得到一些结论：

反证，考虑所有的满足 b_i\le a_i 的方案 b。其中必然有两个和相等的方案，设为 b_1 和 b_2，那么方案 a_i-{b_1}_i+{b_2}_i 和 a_i-{b_2}_i+{b_1}_i 必然有一者的字典序大于 a。

可以知道选择的物品种类数是 B=O(\log W) 的。

  1. 对于两个方案，给两者加上同样的一些物品这一操作是保序的。

由此可以知道，对某个方案，去掉其一些物品，得到的仍然是最优解。

这样就可以 dp，对于所有存在 a_i\ge 2 的方案都可以被转移。这样一来，我们只需要考虑满足 a_i\le 1 的方案。

接下来我们求解 \sum a_i\le B 的方案。

对于某个字典序最大的解，如果我们从前往后地逐个加入其中的物品，其在每个时刻字典序都是最大的。

所以，只需要做 B 次“加入一个物品”的操作即可。

形式化地，设 p_i 为重量为 i 的物品在 a 中的位置，A_i 为是否有重量为 i 的物品，B_i 为是否有重量为 i 的方案。

可以得到加入这个物品之后的方案数组 C=A\times B。这里的困难是，我们还要对 C_k=1 的位置找到有贡献的 A_i 使得 p_i 最小。

首先随一个 p。然后求出每个 C_k 对应的 p_i 在哪个 [2^t,2^{t+1})。这里卷 \log 次就行。

然后是一个关键结论：对于这个区间，有贡献的 A_i 期望数量为 O(\log n)。更具体地说，是以任意的 1-n^{-c} 的概率只有 O(\log n) 个 A_i 有贡献。

大概就是考虑每次把 p 砍半，那么对于一个 C_k，对他有贡献的 A_i 也随机分半了。那么在这里停止当且仅当所有有贡献的 A_i 都丢到大的一边了，有 c\log n 个 A_i 的话概率就只有 n^{-c}。

然后考虑找到所有有贡献的 A_i。使用传统异能 hitting set，即对每个 A_i 以 1/\log n 的概率保留（更保守地，可以以所有 2^{-t} 概率保留），期望 \tilde O(1) 次就能找出所有有贡献的 A_i。

于是就以 \tilde O(W) 的时间解决了！