有 $n$ 个物品, 第 $i$ 个重量为 $a_i$, 求重量不大于 $c$ 的情况下能够装下的最大重量.
$n, m = \max\{a_i\} \leqslant 2 \times 10 ^ 4, c \leqslant 10 ^ 9.$
考虑随便贪心出来一组解 $y$, 设正确答案为 $x$, 显然 $0 \leqslant x - y \leqslant m$.
考虑求最大的 $k \leqslant c - y$, 满足存在一种方案, 删除一些贪心方案中选择的物品, 放入一些贪心方案中没有选择的物品, 总重量的变化量为 $k$. $y + k$ 即为正确答案.
设数列 $\{s_i\}$ 为贪心方案中未选的, 数列 $\{t_i\}$ 为贪心方案中选择了的数的相反数, 其中选择 $t_i$ 用以刻画从原方案中删除 $-t_i$.
注意到以下策略
于是我们发现在转移的过程中, $|k| \leqslant m$ 始终成立. 因此可以导出一个简单的 $\rm DP$
考虑继续优化, 注意到 $0/1$ 单独占一个状态表示位非常浪费, 于是设 $f_{i, k} = j$ 表示在考虑 $s_{1 \sim i}$ 的情况下, 想要表示 $k$, 至少还需要考虑 $t_{1 \sim j}$.
依据前文策略, 考虑两种转移
- 若 $k + a_{i + 1} \leqslant m$, 则考虑是否选择 $a_{i + 1}$, 转移到 $f_{i + 1, k + a_{i + 1}}$ 和 $f_{i + 1, k}$.
- 若 $k > 0$, 则考虑从 $\{t_{i}\}$ 中选择一个数进行转移, 注意到该下标 $p \in [f_{i, k} + 1, f_{i - 1, k}]$.
关于 $p$ 的范围, 首先下界是显然的, 因为如果使用 $t_{f_{i, k}}$ 及之前的数可能会算重. 对于上界, $f_{i - 1, k}$ 进行同样转移时的下界即为 $f_{i - 1, k} + 1$, 又因为表示 $k$ 只需要 $s_{1 \sim i - 1}$ 中的数即可, 若 $f_{i, k}$ 进行转移时使用了 $f_{i - 1, k}$ 转移时使用的同样的 $\{t_{i}\}$ 中的数, 那么一定是不优的, 故没有必要.
关于时间复杂度
总时间复杂度为 $\Theta(nm)$.