Programming

0/1 Knapsack

Pack a mountaineer's rucksack for a deadly ascent. Greedy heuristics chase density and starve on dead weight; the true optimum is a ghost threading a lattice DAG, leaving an insurmountable integrality gap between continuous relaxations and indivisible cargo.

Greedy density starves at 42 while fractional promises 66: how a lattice DAG captures the true 58-value pack.

Mission 15about 8 min

Pack a payload under a hard weight ceiling to beat greedy density heuristics and close the integrality gap.

  1. Compare the greedy density pick (42) against the fractional ceiling (66) on a 10 kg limit
  2. Trace the DPHeatmap lattice to discover the 58-value integer optimum
  3. Take the boss round bet on how scaling values converts exponential DP into a polynomial FPTAS

After thisYou will navigate the boundary between polynomial pseudotime, weak NP-hardness, and approximation schemes.

Short on timeCheck the final cell of the DPHeatmap to compare the 58-value combo (Stove + Food) with greedy's 42.

The Mountaineer’s Dilemma

3 minthe hook

A mountaineer’s pack holds an unforgiving payload limit of ten kilograms. Three indivisible survival supplies lie on the ice before the summit bid:

          weight   value   value per kg
tent         6       42        7.0
stove        5       30        6.0
food         5       28        5.6

The storm tent offers the highest value density by a commanding margin ( points per kilo). Seize it greedily and you burn 6 kg, leaving a 4 kg void too small to fit the 5 kg stove or the 5 kg food. Your haul is locked at 42.

The rucksack holds 10 kg. What is the absolute maximum value achievable by any feasible subset of these three items?

Three candidate answers correspond to meaningful mathematical milestones: 42 from greedy density sorting, 58 from the true integer optimum, and 66 from continuous linear relaxation. The integer reality sits trapped between them.

Keep one picture: the lattice, a grid whose rows are items and whose columns are capacities. Every cell is a take-or-skip decision, and the best pack is the heaviest path from the empty corner to the bottom-right cell.

NextWhy does sorting by density fail when the heaviest high-value item gets stranded?

The Density Trap

2 minthe trap

The natural human instinct is greedy: sort candidates by value-to-weight ratio and cram items in until no more fit. George Dantzig (1957) proved this exact strategy solves the fractional problem where items can be sliced like butter.

In the discrete world, however, items are indivisible atoms. Greedy density optimization falls into catastrophic dead-ends because it cannot foresee how leftover capacity creates stranded voids.

Testing all subsets is viable for three items, but founders into computational oblivion at sixty items. The problem demands an exact method that bypasses combinatorial explosion without falling into greedy traps.

NextHow does Dantzig's continuous relaxation expose the eight-unit integrality gap?

The Lattice DAG

2 minthe invariant

Let denote the maximum value obtainable using a subset of the first items within capacity . For every cell, there are only two possibilities:

Either you skip item and inherit , or you commit kilograms to pack item , pocketing value and inheriting :

This table is not just a ledger of numbers; it is a directed acyclic graph. Every cell is a vertex, downward edges represent decisions to skip, and diagonal jump edges represent decisions to take.

Because every transition advances to the next item index, cycles are impossible. The optimal pack is literally the longest path through this state-space grid (Kellerer, Pferschy & Pisinger 2004).

NextHow does the dynamic programming lattice capture the true 58-value discrete pack?

The Integrality Gap and the Dantzig Relaxation

2 minthe algebra

Look at the complete table evaluated across all capacities:

capacity c:     0   1   2   3   4   5    6    7    8    9   10
items: none     0   0   0   0   0   0    0    0    0    0    0
     + tent     0   0   0   0   0   0   42   42   42   42   42
     + stove    0   0   0   0   0  30   42   42   42   42   42
     + food     0   0   0   0   0  30   42   42   42   42   58

The terminal cell at hits 58, illuminated by a diagonal transition originating from the stove cell at .

1 minboss round

Greedy ratio sorting selects the tent and terminates at 42. Which precise table entry refutes greedy optimality?

Now loosen the indivisibility requirement: allow each item to be fractionally included (). The linear programming relaxation is:

Dantzig’s greedy ratio rule solves this continuous program with exact optimality. Sorting by density yields tent, then stove, then food; the continuous solver takes 100% of the tent (6 kg), then fills the remaining 4 kg with of the stove:

The gap between fractional relaxation (66) and integer optimum (58) is the integrality gap of 8. Because any discrete packing is a valid fractional packing, holds without exception.

NextHow does pseudopolynomial dynamic programming relate to Merkle-Hellman knapsack cryptography?

Stepping the Value Frontier

2 minthe simulation

Drive the interactive matrix below to observe how the dynamic program navigates choices.

1 / 45
filled 0 / 44 cells
capacityitems012345678910nonetentstovefood0000000000000000042424242420000030424242424200000304242424258

Hover or click a cell: its predecessor cells light up and the exact recurrence that filled it appears here. Or press play to walk the fill order(44 cells in dependency order).

best value at capacity 10 = 58

dp[i][j] = max( dp[i−1][j] (skip item i), dp[i−1][j−wᵢ] + vᵢ (take item i) ).

0/1 knapsack, capacity 10.

Four rows, eleven capacity columns, 44 cells. Hover a cell to light the one or two edges that filled it, press play to fill them in dependency order, then press Trace solution from the bottom-right 58 to walk the winning pack back.

Watch the arrows into a cell: a skip comes straight down from the row above, a take comes diagonally from the row above and one capacity to the left; no path ever returns to an earlier row, so no item is counted twice.

Hover over any cell to illuminate the dependency arrows. Press Trace solution from : the recovery path steps , collecting the food and the stove while actively skipping the tent.

Watch column 10 evolve across row iterations: 0, then 42, then 42, and finally jumping to 58. The table only updates when an item can complete a superior combination, cutting through exponential branches in operations.

NextHow do fully polynomial-time approximation schemes scale knapsack instances efficiently?

Budgets, Crypto-Systems, and Cutting Stock

2 minsystems

The 0/1 knapsack recurrence lies at the core of resource allocation under hard ceilings.

Capital budgeting treats funding limits as knapsack capacity, where projects yield discrete returns on fixed costs. In theoretical cryptography, Merkle & Hellman (1978) designed public-key cryptosystems around the knapsack problem, which Adi Shamir (1984) famously broke by transforming modular knapsacks into simultaneous lattice approximations.

The cutting stock problem in manufacturing maps roll lengths directly to knapsack boundaries, trading off scrap waste against production schedules.

Next missionMerge SortScanning 10^9 keys takes 15.8 years; von Neumann's two-finger merge does it in 28.9 seconds with n log n passes.

Pseudopolynomial Illusions and the FPTAS Scaling Magic

Richard Karp (1972) proved that the 0/1 knapsack decision problem is NP-complete. Why then does our dynamic program execute so swiftly in steps?

The nuance lies in how numbers are encoded. An integer capacity requires only bits to specify, meaning the table size is exponential in the length of the input! Algorithms polynomial in numeric magnitude but exponential in input bit-length are termed pseudopolynomial.

Exact DP cell count against the length of the capacity — cells = n(W+1), W = 2^b

1e21e31e41e51e61e71e81e91e101e11510152025bits b used to write the capacity WDP cells n(W + 1)
n = 1000 itemsn = 100 itemsn = 10 items

Because knapsack is only weakly NP-hard, we can build a Fully Polynomial Time Approximation Scheme (FPTAS). Scaling values by and rounding to produces a downscaled instance running in time (Ibarra & Kim 1975; Sahni 1975):

What happens when items can be selected repeatedly? In the unbounded knapsack, the state drops a dimension because previous item history no longer constrains future choices:

Coin change is the min-plus dual: minimise the number of denominations required to form amount :

1 / 34
filled 0 / 33 cells
amountcoin types012345678910none≤ 5≤ 60∞∞∞∞∞∞∞∞∞∞0∞∞∞∞1∞∞∞∞20∞∞∞∞11∞∞∞2

Hover or click a cell: its predecessor cells light up and the exact recurrence that filled it appears here. Or press play to walk the fill order(33 cells in dependency order).

min coins for 10 = 2

dp[i][j] = min( dp[i−1][j] (do not use coin i), dp[i][j−cᵢ] + 1 (use coin i again) ).

Fewest coins making 10 from [5, 6].

Five and six, making ten in two coins. Hover dp[2][6]: the arrow for 'use coin 6 again' comes from the same row, not the row above. That same-row arrow is the unbounded take, and comparing it with the knapsack table is the whole difference between the two problems.

In the 0/1 knapsack table, take-arrows always pull diagonally from the row above to prevent item reuse. In the coin change panel, take-arrows run laterally across the same row, encoding the freedom to draw identical denominations indefinitely.

Attributions

  • Dantzig 1957 — Discrete-variable extremum problems: greedy value-per-kilogram sorting, the continuous LP relaxation, and the discovery of the integrality gap.
  • Karp 1972 — Reducibility among combinatorial problems: proving 0/1 knapsack is NP-complete, establishing weak NP-hardness.
  • Ibarra & Kim 1975 and Sahni 1975 — Value-scaling FPTAS algorithms delivering guarantees in time.
  • Kellerer, Pferschy & Pisinger 2004 — Structural analysis of knapsack variations as DAG longest-path problems.
  • Merkle & Hellman 1978 — Public-key cryptography grounded on subset-sum trapdoors.
  • Shamir 1984 — Cryptanalysis breaking the Merkle–Hellman system in polynomial time.