Bitset Optimization - Resources

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Resources/Dynamic Programming/Bitset Optimization

Bitset Optimization

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.

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

CODEFORCESCareful Maneuvering

CODEFORCESKnights

CODEFORCESDasha and cyclic table

Complexity

If the machine word size is $K$ bits (usually $K = 64$ ), then the complexity becomes:

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

So compared to the standard DP, this improves the constant factor by about $K$ times.

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]);
}