A bag holds only so much weight; each item has a weight and a value; take each or leave it. Maximising the value you carry is NP-complete — no known fast exact method for the general case — yet a dynamic-programming table solves it in weight×items steps. That table is a bounded array, so it runs in real I-13.
THE TECHNIQUE dp[w] = best value in capacity w
Keep a row: for each capacity w, the best value achievable. Add an item by scanning capacities downward (so each item is used once): dp[w] = max(dp[w], dp[w−weight] + value). The last cell is the answer. Watch the row fill. live demo
HISTORY & CREDIT easy to state, hard to solve, easy to approximate
Sounds like a packing puzzle; it is one of the simplest hardest problems — a member of Karp’s original NP-complete list. cited
1897 · George Mathews studies a partition form of the problem; the name “knapsack” is later attributed to Tobias Dantzig. 1950s · Richard Bellman’s dynamic programming gives the pseudo-polynomial O(n·W) table solution shown here. 1972 · Richard Karp lists knapsack among the 21 NP-complete problems — so the DP is only “fast” when the capacity W is small (it is polynomial in the value of W, not its digit-length). practice · it hides inside budgeting, cargo loading, and cutting-stock — solved daily by DP and branch-and-bound.
The gap between “state it” and “solve it fast” is the whole drama of complexity theory. P vs NP
RECOMMEND FOR I-13 dynamic programming, on the array
The DP row is a bounded array; each item scans it downward with indexed reads and writes. It runs:
def item(I dp, I w, I wt, I val, I minw) {
if w < minw { -> dp }
I cand <- dp[w - wt] + val
if cand > dp[w] { dp[w] <- cand }
-> item(dp, w - 1, wt, val, minw)
}
$ i13 run knapsack.i13 # cap 10; items (2,3)(3,4)(4,5)(5,6)
best = 13 # dp[10] after all four items
Recommend:nothing new — a clean no-wall, and a good demonstration of what the array unlocked: a whole class (dynamic programming over a table) that was pure aggregate-wall a week ago now runs from its textbook recurrence. The downward scan (so each item counts once) is exactly the kind of indexed, bounded work I-13’s checked array was built for. Note: a 2-D DP (items × capacity) would want a 2-D array; the corpus’s array is 1-D, so the space-optimized single-row form (shown) is the natural fit — and it is the version practitioners use anyway.