Subset Recurrence

Q. For a set S of n numbers, group the numbers so that each group's sum is at most x, and find the minimum number of groups.

A.
Recurrence

f\left(s\right)\ =\ f\left(s\ \setminus \ p\right)\ \ \text{for}\ \ m\left(s\ \setminus \ p\right)\ +\ a\left[p\right]\ \le \ x

m(s) is the sum of the group with the smallest sum among the groups of set s. Also, since running F(p, 0, n) considers every element that comes in additionally, by the time the inner for loop finishes, m(s) is guaranteed to hold the sum of the group with the smallest sum.

F(s, 1, 1 << n) {
    memo[s] = {n+1, 0};
    F(p, 0, n) if (s & (1 << p)) {
        auto sub = memo[s ^ (1 << p)];
        if (sub.second + a[p] <= x) {
            memo[s] = min(memo[s], {sub.first, sub.second + a[p]});
        } else {
            memo[s] = min(memo[s], {sub.first+1, a[p]});
        }
    }
}

Handy bitmasking properties to keep in mind :

Iterating from 0 to 1<<n goes through every set of n-digit binary numbers, and when A is a subset of B, A always comes first.
If A & B == A, then A is a subset of B.
A & (1 << n) tells you what the (n-1)th digit from the right of A is (starting from the 0th)
When you know the nth digit, you can flip the nth digit with the ^ operator.

Comments