MITM в задаче о рюкзаке
Материал из Algocode wiki
Дана стандартная задача Рюкзак, давайте научимся ее решать за $O(2^{n / 2} * poly(n))$, где $n$ - количество предметов
Решение
Мы умеем ее решать за $O(2^n \cdot n)$, переберём все маски, для каждой проверим полученную стоимость, выберем максимальную из подходящих.
Давайте теперь сделаем тоже самое только для левой части и затем для каждого веса $x$ предпочитаем максимальную стоимость предметов с весом $\le x$ в массиве ans, теперь для каждой маски левой части просто посмотрим сумму предметов - S и массой c и просто проверим S + ans[нужная масса - c]
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin