Knapsack
You've built DP on sequences and grids. Now face capacity constraints and learn to pick or skip items.
Lessons
1. Intro
The Goal
2. 0/1 Knapsack - Problem Statement
The classic
3. 0/1 Knapsack - Why Greedy Fails
The trap
4. 0/1 Knapsack - State Design
Two dimensions
5. 0/1 Knapsack - Base Cases
Empty foundations
6. 0/1 Knapsack - Transition
Take or skip
7. 0/1 Knapsack - Final Answer
Reading the table
8. 0/1 Knapsack - Implementation
The code
9. 0/1 Knapsack - Walkthrough
Tracing the algorithm
10. Lessons from 0/1 Knapsack
summary
11. Challenge: Reconstruct Items
Finding which items were taken
12. Quiz: 0/1 Knapsack Concepts
Knowledge check
13. Applying 0/1 Knapsack
AtCoder DP D
14. Weight-Based to Value-Based
When weights explode
15. Knapsack 2 - Problem Statement
AtCoder DP E
16. Knapsack 2 - Why Weight-Based DP Fails
The constraint trap
17. Knapsack 2 - The Observation
Swap dimensions
18. Knapsack 2 - State Design
Value as index
19. Knapsack 2 - Transition
Minimum weight
20. Knapsack 2 - Implementation
The code
21. Knapsack 2 - Walkthrough
Value-based DP trace
22. Lessons from Value-Based Knapsack
When to swap
23. Quiz: When to Use Value-Based
Choosing the right approach
24. Quiz: Knapsack State Design
Knowledge check
25. 0/1 to Unbounded
Items repeat
26. Unbounded Knapsack - Problem Statement
Infinite copies
27. Unbounded Knapsack - State Design
One dimension
28. Unbounded Knapsack - Transition
Reuse allowed
29. Unbounded Knapsack - Implementation
The code
30. Unbounded Knapsack - Walkthrough
Unlimited items trace
31. Lessons from Unbounded Knapsack
Simplification
32. Quiz: 0/1 vs Unbounded
Comparing variants
33. LeetCode 322 Coin Change - Problem Statement
Apply unbounded
34. LeetCode 322 Coin Change - Walkthrough
Classic unbounded example
35. Quiz: Knapsack Variations
Knowledge check
36. Pattern - Knapsack DP
The framework
37. Book Shop - Problem Statement
Knapsack in disguise
38. Book Shop - Recognizing the Pattern
It's a knapsack
39. Book Shop - State Design
Max pages for budget
40. Book Shop - Walkthrough
Applying the pattern
41. Book Shop - Implementation
Apply 0/1 knapsack
42. What's Next
Preview of variations
43. Section Recap
What we learned
Practice Problems
Classic 0/1 knapsack with a twist on capacity constraints - teaches near-capacity handling
Sliding window optimization for knapsack-like selection problems
Teaches subset selection with contiguity constraints - a partition variant
Bitmask DP knapsack where order matters - teaches state compression
Two-sum knapsack variant tracking which values are achievable as subsets
Multi-constraint knapsack with liquid transfer - complex state design
Knapsack with time constraints and item reconstruction
Prefix-sum optimized knapsack for contiguous segment selection
3D knapsack counting ways - programmer assignment with bug constraints
Classic partition problem that reduces to subset sum - perfect knapsack introduction
Converts to subset sum with positive/negative splits - teaches problem transformation
2D knapsack with two capacity constraints (0s and 1s) - multi-dimensional DP
Disguised partition problem requiring insight to transform into knapsack
Unbounded knapsack counting - teaches difference between combinations and permutations
3D knapsack counting schemes with member and profit constraints
The canonical 0/1 knapsack problem - small capacity, standard state definition.
Knapsack with large capacity but small values - teaches swapping state definition.