The knapsack family

A bag that holds a fixed weight, and items with weights and values: which items should go in? This is the knapsack problem. Its family includes paying an amount with coins, splitting a load into two equal halves, and counting the ways to do any of these. One table, read in slightly different ways, solves them all.

The 0/1 knapsack

There are n items; item i weighs wᵢ kilograms (a whole number) and is worth vᵢ. The bag holds at most W kilograms. Each item is taken whole or not at all, at most once: hence “0/1”. Find the largest total value that fits. GRDY-5 showed that no greedy rule solves this.

Let best[i][x] be the best value using only the first i items, in a bag of x kilograms. Look at the last of those items. It is either skipped, and the best is best[i - 1][x], or taken, if it fits, and then the other items share the x − wᵢ kilograms left: best[i - 1][x - w] + v. Each case uses the best for a smaller problem (lesson 1’s argument), so best[i][x] is the larger of the two. Row 0, with no items, is all 0.

The table has (n + 1)(W + 1) cells, each worked out from two cells of the row above: O(n · W) time.

One row, right to left

Row i reads only row i − 1, so one list can hold the rows one after another (lesson 3). But a cell reads a cell further left, at x − w, and that cell must still hold the old row’s value. Going from the largest bag down to the smallest makes sure of it: the cells to the left have not been updated yet. The second version of the figure shows this.

def knapsack(items, cap):
    best = [0] * (cap + 1)
    for w, v in items:
        for x in range(cap, w - 1, -1):    # right to left
            best[x] = max(best[x], best[x - w] + v)
    return best[cap]

Unlimited copies

The third version of the figure runs the loop from left to right. Then best[x - w] may already include the item, and adding it again uses it twice. For the 0/1 knapsack that is a bug. But when each item has unlimited copies, the unbounded knapsack, it is exactly right: best[x] becomes the best for bag x with any number of copies of the items seen so far.

• Fewest coins (GRDY-5) is an unbounded problem with a minimum instead of a maximum: each coin is an item of value 1, and the bag must be filled exactly.
• At most k copies of an item (the bounded knapsack): split it into bundles of 1, 2, 4, … copies, with a last bundle for the rest, and treat each bundle as one 0/1 item. Any number of copies from 0 to k is a sum of some bundles, so about log₂ k items replace k (log₂ k is the number of times k can be halved before it reaches 1).

Counting and yes-or-no versions

Subset sum asks only whether some items weigh exactly x. Keep True or False instead of a value: can[x] is True if some of the items seen so far weigh exactly x. Python can do this very fast with one whole number used as a row of bits, where bit x is can[x] (BITS explains bits). Shifting the number left by w moves every reachable weight up by w:

def reachable(weights):
    can = 1                    # bit 0: weight 0 is reachable
    for w in weights:
        can |= can << w        # every old weight, plus w
    return can

def even_split(weights):       # the smallest difference
    total = sum(weights)
    can = reachable(weights)
    return min(total - 2 * x for x in range(total // 2 + 1)
               if can >> x & 1)

The work is the same O(n · W), but done 30 or 60 bits at a time inside C. even_split splits a load into two parts whose weights differ as little as possible: the lighter part weighs some reachable x at most half the total.

Counting replaces the maximum with a sum: the number of ways to make x. Here the order of the two loops matters.

• Items (or coins) on the outside, amounts inside: each way is counted once as a set, because the coins are added one value at a time and never in another order. Paying 4 with coins 1, 2 and 3 has 4 ways.
• Amounts on the outside, coins inside: every order is counted separately, as in the footbridge of RECR-P2, where 1 + 2 and 2 + 1 are different orders. Paying 4 has 7 orders.

Both are right; they answer different questions. Read the problem carefully to see which one it asks.

Why big capacities are hard

O(n · W) looks polynomial, but W is a number, not a count of items. Writing W takes only about log₂ W binary digits (the number of times W can be halved), so doubling the length of the input can square W and the time. Such a method is called pseudo-polynomial. With weights near a billion, the table is far too big. In fact the 0/1 knapsack is NP-hard (HARD-1): no method that is polynomial in the length of the input is known. Useful alternatives:

• Small values, big weights: swap the roles. lightest[v] is the least weight that reaches total value v; the answer is the largest v whose weight fits. O(n · V) for a total value V.
• Few items (up to about 40): split the items into two halves and list every choice from each half, with its weight and value. That is 2 to the power n/2 choices per half, about a million for 40 items. Sort one list by weight and keep, for each place, the best value so far; then for each choice in the other list find the best partner that still fits by binary search. This is called meeting in the middle.
• A close answer is enough: round the values down to a coarser scale and run the values table; the result is within any chosen percentage of the best (HARD-4).

Now try DYNP-P8, Ways to pay.