Dynamic programming: the knapsack family

What this chapter covers

Two problems that look almost identical have completely different difficulty, and the knapsack family is where that lesson lands hardest. You have a bag of limited capacity and items with weights and values; maximize the value you carry. If you can take fractions of items — 3 kilos of a 5-kilo gold bar — the problem is solved greedily and optimally: take the densest (value-per-weight) items first, slicing the last one to fill the bag. But if items are all-or-nothing — the 0/1 knapsack — that same greedy rule breaks, and no greedy rule works at all; you need dynamic programming, a table over (items considered, capacity used). This chapter builds both, so you can see precisely where greedy stops working and DP takes over. It also introduces a subtle and important idea: the 0/1 knapsack DP is pseudo-polynomial — fast in practice but not actually polynomial in the input size — which is a first glimpse of the boundary of what dynamic programming can efficiently do.

A bit of history

The knapsack problem is one of the oldest studied in combinatorial optimization, formalized in the early twentieth century and named for the everyday image of packing a rucksack. Its importance grew with two threads. First, it became a canonical NP-hard problem: the 0/1 version is on the list of hard problems that Richard Karp's landmark 1972 paper connected, meaning no known algorithm solves it in time polynomial in the input's bit-length. Second, and in tension with the first, it has a dynamic-programming solution that's efficient whenever the capacity is a modest number — the "pseudo-polynomial" O(n · capacity) algorithm — which made it a favorite teaching example for exactly the subtlety that "efficient in the numbers" and "efficient in the bits" differ. Knapsack also has real cryptographic history: the Merkle-Hellman cryptosystem (1978) based its security on the hardness of a knapsack variant, and its later breaking (by Shamir, using the special structure of that variant) is a cautionary tale about assuming a hard problem stays hard in special cases. The fractional-versus-0/1 split has been the standard illustration of "when does greedy work?" ever since.

The intuition

Fractional knapsack first, because it shows greedy at its best. Sort items by value density — value divided by weight — and take them densest-first. Fill the bag with whole items until one doesn't fit, then take exactly the fraction of it that tops off the remaining space. This is optimal, provably, by an exchange argument: any unit of capacity is best spent on the densest available material, and fractions let you always do exactly that. The greedy-choice property holds cleanly.

Now make items all-or-nothing, and that argument collapses. You can no longer "top off" with a fraction, so taking the densest item first can waste capacity you could have filled better with a combination of less dense items. The classic failure: items (weight 10, value 60), (20, 100), (30, 120) with a bag of 50. Densest first takes the 10-weight item (density 6) then the 20-weight item (density 5), reaching value 160 and using 30 of the 50 capacity — the last item won't fit. The optimum ignores the densest item entirely and takes the 20- and 30-weight items for value 220, filling the bag exactly. Greedy committed to a locally dense choice that globally wasted space. Because no greedy criterion is safe, you must consider, for each item, both possibilities — take it or leave it — and that's the dynamic program. Define dp[i][w] as the best value achievable using the first i items within capacity w. Each item i is either skipped (value dp[i-1][w]) or taken if it fits (value value[i] + dp[i-1][w - weight[i]]), and you take the better. Fill the table from no-items-up and the answer is dp[n][capacity]. Every subset is implicitly considered, but each (item, capacity) subproblem is computed once.

Complexity: how it scales

Fractional knapsack is O(n log n) — a sort plus a sweep. The 0/1 DP is O(n · capacity) time and space: a table of n items by capacity+1 columns, each cell O(1). That looks polynomial, but there's a catch that makes knapsack famous. The face-off doesn't race speed — both are fast — it races the value each method achieves, as items grow large relative to the bag:

The DP is exactly optimal (the flat 100% line, verified against brute force on every small instance). Greedy tracks close to it when items are small relative to the bag — at 10% item size it's essentially optimal — but degrades as items get coarser, falling to about 95% when items can fill the whole bag, because the all-or-nothing granularity is where its wasted space shows. And crucially, 95% is only the average: greedy on 0/1 has no worst-case guarantee at all. The fractional line sits above 100% — at coarse granularity it reports 136% of the 0/1 optimum — because allowing fractions can always do at least as well, and the gap between the fractional relaxation and the true 0/1 answer is a measure of how much the integrality constraint costs. That fractional value is a genuine upper bound on the 0/1 optimum, which is exactly why branch-and-bound solvers use it to prune.

What it's good at, what it isn't

The knapsack DP is the right tool for selecting a maximum-value subset under a single capacity constraint, when the capacity (or total weight) is a modest number: budget allocation, cargo and container loading, cutting-stock and bin-packing subproblems, resource scheduling, portfolio selection under a cost cap, and the subset-sum problem (a special case where value equals weight). Its DP structure also generalizes — bounded knapsack (limited copies of each item), unbounded knapsack (unlimited copies, which is exactly the coin-change recurrence from last chapter), and multi-dimensional knapsack (several constraints) all follow the same take-or-skip pattern. When the constraint is a small integer, this is a clean, exact, and fast solution.

Where it struggles is large capacities, where the pseudo-polynomial O(n · capacity) becomes prohibitive — a capacity in the billions makes the table impossibly large even for few items, and you must switch to branch-and-bound, approximation schemes, or integer-programming solvers. It also handles only the specific structure of independent items and additive value/weight; problems with interactions between items (taking A changes B's value), multiple complex constraints, or non-additive objectives need different formulations. And, as the greedy failure shows, the temptation to solve it with a fast heuristic must be resisted when you need a guaranteed optimum. Knapsack is exactly solvable by DP within its pseudo-polynomial budget, and hard outside it — knowing which regime you're in is the whole game.

The data, or the inputs

The face-off sweeps item size relative to the bag — from tiny items (10% of capacity) to items that can fill it entirely — and measures each method's value as a percentage of the DP optimum, showing greedy degrading as granularity coarsens and the fractional relaxation sitting above 100% as a loose upper bound. Correctness is checked against brute force (try every subset) on hundreds of small instances: the DP must match the true optimum exactly, the reconstructed item set must be a valid packing of that value, greedy must never exceed the optimum, and the fractional value must never fall below it. The animation fills the 2D DP table for four items and capacity 7 — the instance where greedy gets 8 and DP gets 9 — one item-row at a time.

Build it, one function at a time

Fractional knapsack — greedy, and provably optimal for that variant:

def fractional_knapsack(items, capacity):
    """FRACTIONAL knapsack — greedy is optimal here. `items` is a list of (weight, value). Sort by
    value density (value/weight) descending; take whole items until one won't fit, then take the
    fraction that fills the bag. O(n log n). Returns the maximum value (possibly fractional)."""
    order = sorted(items, key=lambda it: it[1] / it[0], reverse=True)   # densest first
    value, room = 0.0, capacity
    for w, v in order:
        if room >= w:
            value += v                            # whole item fits
            room -= w
        else:
            value += v * (room / w)               # take the fraction that fills the bag
            break
    return value

0/1 knapsack — the dynamic program greedy can't replace, with reconstruction:

def knapsack_01(items, capacity):
    """0/1 knapsack — each item taken whole or not at all. Greedy fails; this is dynamic
    programming. dp[i][w] = best value using the first i items within capacity w. Each item is
    either SKIPPED (dp[i-1][w]) or TAKEN if it fits (value + dp[i-1][w-weight]). O(n · capacity)
    time and space — 'pseudo-polynomial': polynomial in the capacity's VALUE, exponential in its
    number of bits. Returns (best_value, chosen_item_indices)."""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w_i, v_i = items[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]               # option A: skip item i
            if w_i <= w:                          # option B: take item i, if it fits
                dp[i][w] = max(dp[i][w], v_i + dp[i - 1][w - w_i])
    # reconstruct which items were taken by walking the table back
    chosen, w = [], capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:              # value changed ⇒ item i was taken
            chosen.append(i - 1)
            w -= items[i - 1][0]
    return dp[n][capacity], sorted(chosen)

Watch it work

Here's the 0/1 DP table for four items (weights 1, 3, 4, 5; values 1, 4, 5, 7) and a bag of capacity 7, filled one item-row at a time. Row 0 is "no items," all zeros. Each new row adds one item and recomputes every capacity column as the better of two choices: skip the item (copy the value straight down from the row above) or take it (its value plus the best value for the leftover capacity, dp[i-1][w-weight]). Green cells are where taking the item won; grey where skipping won. Watch the best value climb as items are added, landing on dp[4][7] = 9 in the bottom-right. The orange trace at the end walks the decisions backward to recover which items were taken — the 3-weight and 4-weight items, value 4+5 = 9. The density-greedy would have grabbed the 5-weight item first (density 1.4) and reached only 8; the table, by considering skip and take at every step, found the better pair greedy's commitment missed:

The complete code

The from-scratch tab is both knapsacks — the fractional greedy and the 0/1 DP with reconstruction; the library tab is the density-greedy applied to 0/1 (the wrong approach, for contrast) and the brute-force optimum used to verify the DP. Flip between them — the fractional greedy and the wrong 0/1 greedy are nearly the same code, and the difference between "optimal" and "no guarantee" is entirely whether fractions are allowed.

"""The knapsack family — pack a bag of limited capacity with items of given weights and values
to maximize the value carried. It's the archetypal constrained-optimization problem, and it hides
a beautiful lesson: two nearly identical versions have completely different difficulty.

FRACTIONAL knapsack lets you take fractions of items (3.5 kg of a 5 kg gold bar). It's solved
GREEDILY and optimally: sort by value-per-weight and take the densest items first, slicing the
last one to fill the bag exactly. The greedy-choice property holds.

0/1 knapsack forces an all-or-nothing choice per item (you take the whole gold bar or none). That
one change destroys the greedy-choice property — taking the densest item first can be arbitrarily
bad — and the problem becomes one that only DYNAMIC PROGRAMMING solves exactly, via a table over
(items considered, capacity used). This chapter builds both, so the fractional/0-1 split shows
exactly where greedy stops working and DP takes over.
"""


# region: fractional
def fractional_knapsack(items, capacity):
    """FRACTIONAL knapsack — greedy is optimal here. `items` is a list of (weight, value). Sort by
    value density (value/weight) descending; take whole items until one won't fit, then take the
    fraction that fills the bag. O(n log n). Returns the maximum value (possibly fractional)."""
    order = sorted(items, key=lambda it: it[1] / it[0], reverse=True)   # densest first
    value, room = 0.0, capacity
    for w, v in order:
        if room >= w:
            value += v                            # whole item fits
            room -= w
        else:
            value += v * (room / w)               # take the fraction that fills the bag
            break
    return value
# endregion


# region: knapsack_01
def knapsack_01(items, capacity):
    """0/1 knapsack — each item taken whole or not at all. Greedy fails; this is dynamic
    programming. dp[i][w] = best value using the first i items within capacity w. Each item is
    either SKIPPED (dp[i-1][w]) or TAKEN if it fits (value + dp[i-1][w-weight]). O(n · capacity)
    time and space — 'pseudo-polynomial': polynomial in the capacity's VALUE, exponential in its
    number of bits. Returns (best_value, chosen_item_indices)."""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w_i, v_i = items[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]               # option A: skip item i
            if w_i <= w:                          # option B: take item i, if it fits
                dp[i][w] = max(dp[i][w], v_i + dp[i - 1][w - w_i])
    # reconstruct which items were taken by walking the table back
    chosen, w = [], capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:              # value changed ⇒ item i was taken
            chosen.append(i - 1)
            w -= items[i - 1][0]
    return dp[n][capacity], sorted(chosen)
# endregion


# region: table
def knapsack_table(items, capacity):
    """Return the full dp table plus, for each cell, whether the current item was TAKEN there —
    used to animate the fill and see the take/skip decision pattern."""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    taken = [[False] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w_i, v_i = items[i - 1]
        for w in range(capacity + 1):
            skip = dp[i - 1][w]
            take = v_i + dp[i - 1][w - w_i] if w_i <= w else -1
            if take > skip:
                dp[i][w], taken[i][w] = take, True
            else:
                dp[i][w] = skip
    return dp, taken
# endregion

"""The contrasts and the reference. Two things to compare 0/1 knapsack's DP against:

- `greedy_01` applies the FRACTIONAL greedy (densest first) to the 0/1 problem — the natural wrong
  idea. It's fast but can leave a lot of value on the table, and it's the cautionary contrast that
  shows why 0/1 needs DP.
- `brute_force_01` tries every subset (O(2^n)) for the true optimum — the reference that proves the
  DP is correct on small instances.

In production you'd use the DP (or an ILP/branch-and-bound solver for large instances); these exist
to verify and to contrast.
"""
from itertools import combinations


# region: greedy
def greedy_01(items, capacity):
    """The fractional greedy (densest item first) applied to 0/1 — WRONG in general. It takes whole
    dense items until none fits, never reconsidering, so it can miss a better combination of less
    dense items that pack the bag more fully. Returns (value, chosen indices)."""
    order = sorted(range(len(items)), key=lambda i: items[i][1] / items[i][0], reverse=True)
    value, room, chosen = 0, capacity, []
    for i in order:
        w, v = items[i]
        if w <= room:
            value += v
            room -= w
            chosen.append(i)
    return value, sorted(chosen)
# endregion


# region: brute
def brute_force_01(items, capacity):
    """The true 0/1 optimum by trying every subset — O(2^n), only for verification on small inputs.
    Returns the best value."""
    n = len(items)
    best = 0
    for r in range(n + 1):
        for subset in combinations(range(n), r):
            w = sum(items[i][0] for i in subset)
            if w <= capacity:
                best = max(best, sum(items[i][1] for i in subset))
    return best
# endregion

Scratch vs library

The knapsack pair is the sharpest illustration in this book of when greedy works. Fractional and 0/1 knapsack differ by a single rule — can you take a fraction? — and that rule is the difference between a provably-optimal one-line greedy and an NP-hard problem needing a DP table. It makes concrete the greedy chapter's abstract point: greedy is optimal exactly when the problem has the greedy-choice property, and "take fractions" is precisely what gives fractional knapsack that property and 0/1 knapsack lacks. The chapter also draws the boundary of dynamic programming itself. DP solved 0/1 knapsack pseudo-polynomially — efficient for modest capacities but not truly polynomial — which is the first sign that DP, powerful as it is, doesn't make every problem easy; it makes the state space explicit, and when that space is large (capacity in the billions, or the exponential subsets-of-cities state of the traveling salesman), DP helps but doesn't rescue you. In production you'd use the DP for small capacities and branch-and-bound or an ILP solver otherwise; building both knapsacks yourself is what makes the fractional/0-1 divide — one of the most important "is-this-greedy-or-DP?" distinctions — something you've seen rather than memorized.

Where you'll actually meet it

Knapsack problems are everywhere resources are allocated under a budget. Cargo, container, and vehicle loading optimize value under weight or volume limits. Financial portfolio selection maximizes return under a cost cap (a knapsack variant). Cloud and cluster schedulers pack jobs onto machines under CPU/memory constraints (multi-dimensional knapsack, bin-packing). Cutting-stock and manufacturing minimize waste by packing orders. Ad selection and media scheduling maximize value under a slot or budget limit. Subset-sum — a knapsack special case — appears in accounting reconciliation and cryptography. And the DP technique itself, take-or-skip over a capacity, recurs across resource-optimization software. The fractional version shows up wherever divisible resources are allocated by density (fractional flows, some scheduling). Whenever the question is "maximum value under a capacity limit," a knapsack model is likely underneath.

Takeaways

The knapsack family teaches where greedy ends and dynamic programming begins. Fractional knapsack — items divisible — is greedy-optimal: take the densest first. 0/1 knapsack — all-or-nothing — destroys the greedy-choice property (density-greedy has no worst-case guarantee and can be arbitrarily bad) and needs a DP table, dp[i][w] = max(skip, take), O(n · capacity). That complexity is pseudo-polynomial — polynomial in the capacity's value but exponential in its bit-length — so knapsack is NP-hard yet efficiently solvable for modest capacities, a crucial distinction between "fast for my inputs" and "polynomial-time." One rule, fractions or not, decides the whole difficulty.

The next chapter keeps DP on two-dimensional tables but moves from packing to sequences. Edit distance and longest common subsequence measure how similar two strings are by filling a grid where each cell compares one character of each string — the algorithms behind spell-checkers, diff, autocorrect, and DNA sequence alignment. Like knapsack, they're DP over a two-dimensional state; unlike knapsack, that state is genuinely polynomial, and the problems are among the most useful in all of computing.