Главная Курсы Ресурсы Задачи Национальная олимпиада Соревнования Таблица лидеров

...

Главная/Resources/Dynamic Programming/Оптимизация битового набора

Оптимизация битового набора

Задача о рюкзаке

Предположим, что нам даны $N$ предметов, и $i$ -й предмет имеет вес $w_i$ .

Мы хотим определить, существует ли подмножество предметов, суммарный вес которого ровно равен $W$ .

Стандартное решение динамическим программированием использует массив d, где:

d[x] = 1 означает, что суммарный вес x достижим;
d[x] = 0 иначе.

Обычный код выглядит так:

Использование `std::bitset`

Мы можем хранить массив DP с помощью std::bitset.

Основная идея в том, что сдвиг битсета на w[i] позиций соответствует добавлению веса w[i] ко всем текущим достижимым суммам.

Поэтому переход становится:

Внешние задачи

Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:

CODEFORCESCareful Maneuvering

CODEFORCESKnights

CODEFORCESDasha and cyclic table

Оптимизация битового набора - Resources

Эта версия короче и обычно намного быстрее на практике, потому что битовые операции выполняются сразу над целыми машинными словами.

Сложность

Если размер машинного слова равен $K$ бит (обычно $K = 64$ ), то сложность становится:

O\left(\frac{N \cdot W}{K}\right)

Так что по сравнению со стандартным DP это улучшает константный множитель примерно в $K$ раз.

d[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        d[j] |= d[j - w[i]];
    }
}

d[0] = 1;
for (int i = 0; i < n; i++) {
    d |= (d << w[i]);
}