Задача о рюкзаке
Предположим, что нам даны предметов, и -й предмет имеет вес .
Мы хотим определить, существует ли подмножество предметов, суммарный вес которого ровно равен .
Стандартное решение динамическим программированием использует массив d, где:
d[x] = 1означает, что суммарный весxдостижим;d[x] = 0иначе.
Обычный код выглядит так:
Использование std::bitset
Мы можем хранить массив DP с помощью std::bitset.
Основная идея в том, что сдвиг битсета на w[i] позиций соответствует добавлению веса w[i] ко всем текущим достижимым суммам.
Поэтому переход становится: