Bitsets: subset sums by shifting

A bitset keeps a set of small integers as the bits of one long integer, or of an array of machine words, so a whole set can be shifted, combined or tested in a few word operations. Subset sums are the classic use: keep every load that some group of items can make as a 1 bit, and adding an item of weight w moves every load up by w at once, a shift. That replaces a table of n × C booleans with n shifts of C bits, 64 bits a step on a 64-bit machine and much more than that in Python, where a big-integer shift runs in C. Here are the problems, their brute force with its cost, and what to notice.

Two loading problems

Problem A: fill a truck exactly. A courier hub has n ≤ 200 parcels of whole-kilogram weights from 1 to 2,000. Can some of them weigh exactly C kilograms, for a truck of capacity C ≤ 2 × 10⁵? With the parcels [3, 1, 4, 2, 2], C = 6 gives yes and C = 13 gives no, because all five together weigh only 12.

Problem B: split evenly. Can all the parcels go onto two trucks that carry exactly the same weight? [3, 1, 4, 2, 2] gives yes, with 4 + 2 on one truck and 3 + 1 + 2 on the other; [5, 3] and [1, 2, 5] give no.

The brute force, and why it fails at these sizes

Trying every group of parcels answers both questions, and nobody doubts it:

# Both problems by brute force: try every subset of the parcels and add up its weight.
from itertools import combinations


def fills_exactly_brute(weights, capacity):
    """Problem A: does some subset weigh exactly capacity? Returns the answer and the subsets tried."""
    tried = 0
    for k in range(len(weights) + 1):
        for subset in combinations(weights, k):
            tried += 1
            if sum(subset) == capacity:
                return True, tried
    return False, tried


def splits_evenly_brute(weights):
    """Problem B: can the parcels go into two trucks of exactly equal weight?"""
    total = sum(weights)
    return total % 2 == 0 and fills_exactly_brute(weights, total // 2)[0]


print("A:", fills_exactly_brute([3, 1, 4, 2, 2], 6), "  ([3, 1, 4, 2, 2], capacity 6)")
print("A:", fills_exactly_brute([3, 1, 4, 2, 2], 13), "  (capacity 13)")
for weights in ([3, 1, 4, 2, 2], [5, 3], [1, 2, 5]):
    print("B:", weights, "->", splits_evenly_brute(weights))
print(f"at n = 200 there are 2^200 = {2**200:.3e} subsets")

A: (True, 14)   ([3, 1, 4, 2, 2], capacity 6)
A: (False, 32)   (capacity 13)
B: [3, 1, 4, 2, 2] -> True
B: [5, 3] -> False
B: [1, 2, 5] -> False
at n = 200 there are 2^200 = 1.607e+60 subsets

Five parcels have 32 groups. Two hundred have 2²⁰⁰, about 1.6 × 10⁶⁰, more than any computer will ever enumerate. The usual repair is a table of booleans, one row per parcel and one column per load from 0 to C, which needs 200 × 200,001 = 40,000,200 cells at the limits: fine in C++, slow in Python, and still one cell at a time.

What to notice

• The answers are a set of small integers: the loads from 0 to C that some group reaches. A set of small integers fits in the bits of one big number, bit s for load s.
• Adding a parcel of weight w keeps every load and adds every load plus w, the same operation on every member of the set: a shift of the whole set by w, combined with the set itself.
• Problem B is problem A with C equal to half the total, after checking that the total is even.

Reachable loads as bits: reach | (reach << w), proved Pro: opens with a Pro, Premium or Ultimate pass