Knapsack Problem, in depth: 0/1, unbounded and bounded DP, reconstruction, meet-in-the-middle, branch and bound and approximation

The variants

Several problems share the name, and the right algorithm depends on which one you have:

Only the fractional variant is solved optimally by greedy filling in value-per-weight order, in O(n log n). It reappears later as a bound for the 0/1 problem.

Why greedy fails for 0/1

Use this running example throughout: capacity W = 7, and four items given as (weight, value): A (1, 1), B (3, 4), C (4, 5), D (5, 7). The value densities are D 1.40, B 1.33, C 1.25 and A 1.00.

Greedy by density takes D (weight 5, value 7), then cannot fit B or C in the remaining 2 units, then takes A: total value 8. The optimum is B + C, weight 7, value 9. Greedy took the densest item first, leaving a 2-unit gap nothing valuable could fill. Whether an item is worth taking depends on what else fits beside it, and that dependence on remaining capacity is what dynamic programming tracks. The general theory of when greedy choices are safe is covered in the greedy algorithms guide.

The 0/1 recurrence and a worked table

Define dp[i][c] as the best value achievable using only the first i items with capacity c. For item i with weight w and value v there are two choices. Skip it, and the best is dp[i-1][c]. Take it, which needs w ≤ c, and the best is dp[i-1][c-w] + v. So:

dp[0][c] = 0                                        for every c
dp[i][c] = dp[i-1][c]                               if w_i > c
dp[i][c] = max(dp[i-1][c], dp[i-1][c - w_i] + v_i)  otherwise
answer   = dp[n][W]

Both choices read row i-1, so the take branch adds v to a solution that cannot already contain item i. That enforces "at most once". The example's table:

The last row answers every smaller budget for free: capacity 5 gives 7 (D), 6 gives 8 (D and A).

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]
            if w <= c and dp[i - 1][c - w] + v > dp[i][c]:
                dp[i][c] = dp[i - 1][c - w] + v
    # walk back up: a value that differs from the row above means item i was taken
    chosen, c = [], W
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:
            chosen.append(i - 1)
            c -= weights[i - 1]
    return dp[n][W], chosen[::-1]

knapsack_01([1, 3, 4, 5], [1, 4, 5, 7], 7)   # (9, [1, 2]) -> items B and C

Time and space are both O(nW). The reconstruction needs the full table; that is the price of knowing which items were chosen rather than only the best value.

One row, and why loop direction matters

Each row reads only the row above, so one array of size W + 1 is enough if you update it in the right order. For 0/1, iterate capacity from high to low. When you compute best[c], the entry best[c - w] has not been updated for this item yet, so it still holds the previous row's value, and the item cannot be counted twice. Iterate from low to high and best[c - w] may already include the current item, which allows unlimited copies. That accidental behaviour is exactly the unbounded knapsack, so the two variants differ by one loop direction:

def knapsack_01_value(weights, values, W):
    best = [0] * (W + 1)
    for w, v in zip(weights, values):
        for c in range(W, w - 1, -1):      # descending: each item at most once
            best[c] = max(best[c], best[c - w] + v)
    return best[W]

def knapsack_unbounded(weights, values, W):
    best = [0] * (W + 1)
    for w, v in zip(weights, values):
        for c in range(w, W + 1):          # ascending: best[c - w] may already use this item
            best[c] = max(best[c], best[c - w] + v)
    return best[W]

For the example the unbounded optimum at capacity 7 is also 9 (for instance B + B + A), which is a reminder that matching outputs on one test case prove little. Capacity 2 separates them: 0/1 gives 1, unbounded gives 2 (A + A). Write tests where the variants disagree. The O(W) version loses reconstruction; to recover items, store one taken-or-not bit per cell.

Bounded knapsack by binary splitting

If item i may be used up to k_i times, the naive approach expands it into k_i separate 0/1 items, which is slow when k_i is large. Binary splitting replaces k copies with bundles of 1, 2, 4, ... copies plus a remainder. Any count from 0 to k can be formed from a subset of these bundles, so the 0/1 algorithm over the bundles solves the bounded problem with O(log k) items per original item.

def split_bounded(weights, values, counts):
    bundles = []
    for w, v, k in zip(weights, values, counts):
        size = 1
        while k > 0:
            take = min(size, k)            # k = 10 becomes bundles of 1, 2, 4 and 3
            bundles.append((w * take, v * take))
            k -= take
            size *= 2
    return bundles                          # feed these to the 0/1 algorithm

A monotonic-queue technique reaches O(nW), but binary splitting is simpler and usually fast enough.

Pseudo-polynomial: what O(nW) really costs

O(nW) looks polynomial, but W is written in about log2(W) bits, so one more bit doubles the table. With n = 100 and W = 10^9 that is 10^11 cell updates for an input of a few hundred numbers. This pseudo-polynomial time is why knapsack is NP-hard despite the fast DP. The same trap applies to subset sum, which is knapsack with value equal to weight.

So before choosing an algorithm, look at the numbers:

• Small W (up to roughly 10^7 with a one-dimensional array): DP over capacity.
• Large W, small total value: swap the roles. Let minw[s] be the least weight achieving value exactly s, run the same descending loop over value, and answer with the largest s whose minimum weight is at most W. Cost O(n times total value).
• Large W and values, n up to about 40: meet-in-the-middle.
• Large everything, need the exact optimum: branch and bound or an integer programming solver.
• Large everything, near-optimal is fine: the FPTAS, or greedy with a fix-up step.

If all weights share a common factor, divide them and W by their greatest common divisor first.

Meet-in-the-middle for n up to about 40

2^40 subsets is too many, but 2^20 is about a million. Enumerate subsets of each half; for each left subset of weight w, binary search the right subsets (sorted by weight, dominated ones removed) for the best one weighing at most W - w. Time is O(2^(n/2) n), independent of W and of the values.

from bisect import bisect_right

def knapsack_mitm(items, W):                       # items: list of (weight, value)
    def subsets(part):
        res = [(0, 0)]
        for w, v in part:
            res += [(sw + w, sv + v) for sw, sv in res if sw + w <= W]
        return res

    half = len(items) // 2
    left, right = subsets(items[:half]), subsets(items[half:])
    right.sort()
    ws, vs, running = [], [], -1
    for w, v in right:                             # keep a strictly improving frontier
        if v > running:
            ws.append(w); vs.append(v); running = v
    best = 0
    for w, v in left:
        j = bisect_right(ws, W - w) - 1            # heaviest frontier point that still fits
        if j >= 0:
            best = max(best, v + vs[j])
    return best

Branch and bound with the fractional bound

Branch and bound searches the take-or-skip tree depth first and prunes branches whose optimistic bound cannot beat the best solution so far. The classic bound is the fractional relaxation: whole items by density while they fit, then a fraction of the next. No 0/1 solution can exceed it.

In the example, the root bound is D (7) plus two-thirds of B (2.67), so 9.67. As soon as the search finds a value-9 solution, any branch whose bound is at most 9 is cut. Because values are integers, a bound of 9.67 can never produce more than 9, so you can floor the bound and prune even harder.

def knapsack_bb(items, W):                          # items: list of (weight, value), weights > 0
    items = sorted(items, key=lambda it: it[1] / it[0], reverse=True)
    n, best = len(items), 0

    def bound(i, cap, val):
        for w, v in items[i:]:
            if w <= cap:
                cap -= w; val += v
            else:
                return val + v * cap / w            # fraction of the first item that does not fit
        return val

    def search(i, cap, val):
        nonlocal best
        best = max(best, val)
        if i == n or bound(i, cap, val) <= best:
            return
        w, v = items[i]
        if w <= cap:
            search(i + 1, cap - w, val + v)         # try take first: finds good incumbents early
        search(i + 1, cap, val)

    search(0, W, 0)
    return best

Worst-case time is exponential, but the bound usually prunes most of the tree. Integer programming solvers apply the same idea with far stronger bounds, so try one before writing your own. This is also the template for backtracking with pruning.

Approximation: the FPTAS

Knapsack has a fully polynomial-time approximation scheme. Pick an error tolerance eps, scale every value down by K = eps times v_max / n and round down, then solve exactly with the value-indexed DP. The scaled values sum to at most n^2 / eps, so the DP runs in O(n^3 / eps) whatever the size of W. The rounding loses at most K per item, n times K = eps times v_max in total, and v_max is no larger than the optimum provided items heavier than W have been removed first. The result is at least (1 - eps) times the optimum.

def knapsack_fptas(weights, values, W, eps):
    items = [(w, v) for w, v in zip(weights, values) if w <= W]   # needed for the guarantee
    n, vmax = len(items), max(v for _, v in items)
    K = eps * vmax / n
    scaled = [int(v // K) for _, v in items]
    total = sum(scaled)
    minw = [0] + [float("inf")] * total             # least weight that reaches scaled value s
    for (w, _), s in zip(items, scaled):
        for t in range(total, s - 1, -1):
            minw[t] = min(minw[t], minw[t - s] + w)
    return max(t for t in range(total + 1) if minw[t] <= W)      # scaled optimum

To return real items, keep a choice record per cell and sum the original values of the reconstructed set. In practice a MIP solver with a time limit is more common, but the FPTAS is the cleanest proven trade of accuracy for time.

Failure modes

What to do next

1. Classify your problem: 0/1, unbounded, bounded, fractional, multi-dimensional or group, and write the variant down.
2. Measure n, W and the total value, and pick the method from the size rules above before writing code.
3. Implement the 2-D 0/1 DP with reconstruction, and check it on the worked example (value 9, items B and C).
4. Add the 1-D versions and tests where 0/1 and unbounded disagree, such as W = 2 in the example.
5. For large inputs, try a MIP solver with a time limit before hand-writing branch and bound.
6. Practise on related problems: target sum and subset sum both reduce to the same table.