Оптимизатсияи битсет

Knapsack Problem

Suppose we are given $N$ items, and the $i$-th item has weight $w_i$.

We want to determine whether there exists a subset of items whose total weight is exactly $W$.

A standard dynamic programming solution uses an array d, where:

• d[x] = 1 means that a total weight of x is reachable;
• d[x] = 0 otherwise.

The usual code looks like this:

Using std::bitset

We can store the DP array using std::bitset.

The main idea is that shifting the bitset by w[i] positions corresponds to adding the weight w[i] to all currently reachable sums.

So the transition becomes:

This version is shorter and usually much faster in practice, because bit operations are performed on whole machine words at once.