Рюкзак за Ssqrt

Если у нас есть $n$ предметов с весами $w_1, w_2, \ldots, w_n$, таких что $w_1 + w_2 + \ldots + w_n = S$, то мы можем решить задачу о рюкзаке за время $O(Sn)$ стандартной динамикой. Как решать быстрее? Попытаемся сделать так, чтобы $n$ было $O(\sqrt{S})$.

Заметим, что количество различных весов среди $w_1, w_2, \ldots, w_n$ будет $O(\sqrt{S})$, потому что если среди них $k$ различных чисел, то $S = w_1 + w_2 + \ldots + w_n \geq 1 + 2 + \ldots + k = \frac{k(k + 1)}{2}$, значит $k \leq \sqrt{2S}$.

Рассмотрим некоторый вес $x$, который встречается в наборе весов. Обозначим за $c$ его количество вхождений. Рассмотрим такое максимальное натуральное $t$, что $2^t - 1 \leq c$. Тогда в наборе весов $c$ вхождений веса $x$ заменим на веса $x, 2x, \ldots, 2^{t-1}x, (c+1-2^t)x$. Легко видеть, что все суммы $0, x, \ldots, cx$ можно по-прежнему набрать и только их.

Уже сейчас легко видеть, что новое количество весов будет $O(\sqrt{S}\log{S})$, потому что для каждого веса мы оставили $\leq \log{S}$ весов, а различных весов $O(\sqrt{S})$. Для нужной нам оценки посмотрим, для каких $x$ мы могли сделать замену на $\geq p$ весов (при $p \geq 2$)? Мы всегда добавляем $t+1$ число, то есть $p-1 \leq t$, то есть $2^{p-1} \leq 2^t \leq с+1$. Значит количество вхождений каждого из таких $x$ будет $\geq 2^{p-1}-1$, значит их сумма $\leq \frac{S}{2^{p-1}-1} \leq \frac{4S}{2^p}$, значит количество $\leq \sqrt{8S} \frac{1}{\sqrt{2}^p}$ (потому что они все различны, как мы помним). Значит в сумме мы добавим $\leq \sqrt{8S} (\sum\limits_{p=2}^{\log{S}}{\frac{1}{\sqrt{2}^p}})$ чисел, что является $O(\sqrt{S})$.

Bonus: если далее делать рюкзак с помощью $bitset$, то получаем решение за $O(\frac{S\sqrt{S}}{64})$.

Автор конспекта: Иван Сафонов

По всем вопросам пишите в telegram @isaf27