Stage 1 · Code
Dynamic Programming
Knapsack
0/1 Knapsack, unbounded knapsack, and space-optimized solutions.
7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
0/1 Knapsack
Given items with weight and value, max weight capacity W. Choose subset maximizing total value without exceeding W. Each item used at most once.
Go0/1-knapsack-2d-dp.go
23 linesLn 1, Col 1Go
dp[i][cap] = max value using first i items with capacity cap. Choice: skip item i (dp[i-1][cap]) or take it (dp[i-1][cap-w] + v). O(nW) time/space.
Unbounded Knapsack
Each item can be used unlimited times. Transition uses dp[i][cap-w] (same row i, not i-1). Allows multiple of same item.
Gounbounded-knapsack.go
13 linesLn 1, Col 1Go
1D array sufficient. Iterate capacity forward (w to W) so dp[cap-w] is already updated for current item (allows reuse). O(nW) time, O(W) space.
Space Optimization
0/1 knapsack: iterate capacity backward (W to w) to use dp[cap-w] from previous row. Unbounded: iterate forward to reuse same item.
| Variant | Dimension | Iteration | Space |
|---|---|---|---|
| 0/1 Knapsack | 2D or 1D | Backward (W..w) | O(W) |
| Unbounded | 1D | Forward (w..W) | O(W) |
| Multiple knapsack (k copies) | 1D | Binary split + backward | O(W) |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.