Algorithms
Knapsack: The Knapsack Problem
Цели урока
- Understand the 0/1 Knapsack formulation
- Implement recursive and DP solutions
- Optimize space to O(W)
- Understand difference between 0/1 vs Unbounded
- Solve variations: Subset Sum, Coin Change
Предварительные знания
- Dynamic Programming
The knapsack problem is one of the most important in combinatorial optimization. Cryptographers study it (foundation of some ciphers), economists (portfolio optimization), logistics (container loading). In interviews - must know.
- Truck and container loading
- Investment portfolios
- Resource allocation
- Cryptography (Merkle-Hellman)
History of the Knapsack Problem
The problem was formalized in 1897 by Tobias Dantzig. Proven NP-complete in 1972 (Karp). Despite this, the O(nW) DP solution works fast for practical cases - it's a pseudo-polynomial algorithm.
Problem Statement
**Knapsack problem:** n items with weights and values. Knapsack capacity W. Which items to take to maximize total value?
**Problem variants:**
- **0/1 Knapsack** - each item can be taken 0 or 1 times
- **Unbounded Knapsack** - items can be taken unlimited times
- **Bounded Knapsack** - each item has its own limit
- **Fractional Knapsack** - can take fractions of items (greedy!)
**0/1 Knapsack is NP-complete!** But the pseudo-polynomial DP solution works fast for reasonable W.
How does 0/1 Knapsack differ from Fractional Knapsack?
Recursive solution
**For each item, two choices:** take it or not.
Why is the recursive solution O(2^n)?
DP solution: 2D table
**dp[i][w]** = maximum value using the first i items with capacity w.
**Reconstructing selected items:**
weights=[2,3,4], values=[3,4,5], W=5. Maximum value?
Optimization to O(W) space
**Key observation:** dp[i][w] depends only on dp[i-1][...]. One row is enough!
**Unbounded Knapsack - unlimited repetitions:**
**0/1 → right to left. Unbounded → left to right.** Direction determines whether an item can be reused.
Why do we iterate w right to left in 0/1 Knapsack?
Variations and Applications
**Subset Sum - special case of Knapsack:**
**Coin Change - Unbounded variation:**
**Pattern:** many problems reduce to Knapsack. Subset Sum, Partition, Coin Change, Target Sum - all are variations.
The problem 'can you split an array into two parts with equal sum' is:
Knapsack
- 0/1: each item 0 or 1 times
- DP: dp[i][w] = max(don't take, take)
- Optimization: one row, iterate right to left
- Unbounded: left to right (repetitions)
- Subset Sum, Coin Change - variations
Related Topics
Knapsack is a central optimization problem.
- DP Basics — Base paradigm
- Greedy Algorithms — Fractional Knapsack is solved greedily
- NP-completeness — Knapsack is NP-complete
Связанные уроки
- alg-21-dp — Knapsack is the model 2D DP optimization problem
- alg-20-greedy — Greedy solves fractional knapsack but fails 0/1
- alg-34-approximation — Knapsack admits an FPTAS approximation scheme
- crypto-24-rsa-math — Knapsack hardness underlies early public-key cryptosystems
- ml-01-intro