Knapsack and optimisation problems
Knapsack problems ask how to choose items under a limit to maximise value. They show both the power of DP and its limits.
The 0/1 knapsack problem
Given items with weights and values and a bag of capacity W, choose a subset with total weight at most W and maximum total value; each item is taken whole or not at all. Trying all subsets takes O(2^n). A greedy choice by value-to-weight ratio can fail, because a high-ratio small item may block a better combination.
The knapsack recurrence
State: K[i][w] = best value using the first i items with capacity w. Either skip item i, giving K[i - 1][w], or take it if it fits, giving value[i] + K[i - 1][w - weight[i]]. K[i][w] is the larger of these. The table has (n + 1)(W + 1) entries, each O(1), so the algorithm takes O(nW) time.
Pseudo-polynomial time
O(nW) looks polynomial, but W is a number, and writing it needs only about log2(W) bits. If capacities are huge, say 10^15, the table is impractically large. Such algorithms are called pseudo-polynomial. The 0/1 knapsack decision problem is NP-complete, so no truly polynomial algorithm is known.
Variants
In the unbounded knapsack, each item can be used any number of times, so K[w] = max over items of value + K[w - weight]. The fractional knapsack, where items can be split, is solved exactly by the greedy ratio method in O(n log n). Subset sum, deciding if some subset reaches exactly a target, is a knapsack special case.
DP on trees and DAGs
DP works on any structure whose subproblems form a DAG with no circular dependencies. On a tree, compute answers for children before parents: for example, the maximum independent set of a tree, the largest set of vertices with no two adjacent, uses two values per node, with and without that node. Longest paths in DAGs follow a topological order.
Bitmask DP and its limits
When the state includes a subset of up to about 20 items, encode it as a bitmask. The Held-Karp algorithm solves the travelling salesperson problem exactly in O(n^2 2^n), much better than the n! of brute force but still exponential, practical only for a few dozen cities. Such state explosions mark the boundary of what DP can do.
DP in practice
Dynamic programming appears in speech recognition (the Viterbi algorithm for hidden Markov models), bioinformatics sequence alignment (Needleman-Wunsch and Smith-Waterman), text justification in word processors, resource allocation, and reinforcement learning, where Bellman's equations define optimal decision policies.
Worked example
Capacity 5; items A (weight 2, value 3), B (weight 3, value 4), C (weight 4, value 5). Greedy by ratio picks A (1.5), then B (1.33): weight 5, value 7. Checking with DP: K[3][5] = max(K[2][5], 5 + K[2][1]) = max(7, 5 + 0) = 7. So the best value is 7, using A and B. Taking C alone gives only 5, because nothing else then fits.
Key takeaways
The 0/1 knapsack maximises value under a weight limit; brute force is O(2^n) and greedy by ratio can fail. The DP K[i][w] = max(skip, take) runs in O(nW), which is pseudo-polynomial since W is a magnitude; the problem is NP-complete. Unbounded knapsack reuses items; fractional knapsack is solved greedily; subset sum is a special case. DP works on trees and DAGs with acyclic dependencies. Bitmask DP, such as Held-Karp's O(n^2 2^n) travelling salesperson algorithm, shows exponential limits. DP powers Viterbi decoding, sequence alignment, and reinforcement learning.
Flashcard
Take each item whole or not at all
Check your understanding
Why is the O(nW) knapsack algorithm called pseudo-polynomial?