The 0/1 Knapsack Problem & 2D Grid Dynamic Programming
Master 2D dynamic programming patterns. Solve 0/1 Knapsack, optimize space to a single 1D row, and solve Longest Common Subsequence (LCS).
By the end, you’ll be able to…
- Formulate the 0/1 Knapsack recurrence relation and construct the 2D DP state table.
- Optimize 0/1 Knapsack from O(N * W) space to O(W) space by traversing the table backward.
- Implement the Longest Common Subsequence (LCS) algorithm.
01The 0/1 Knapsack Problem Formulation
The 0/1 Knapsack Problem is the quintessential 2D Dynamic Programming challenge. Given N items, each with a weight w[i] and a value v[i], and a knapsack with maximum weight capacity W, determine the maximum value that can be packed into the knapsack.
For each item, we have a binary choice: either include it (1) or exclude it (0). We cannot take fractions of an item. A brute-force exploration of all 2^N combinations takes exponential time. Using 2D DP, we solve it in pseudo-polynomial O(N * W) time.
022D DP State Table Construction
We construct a 2D table dp[N + 1][W + 1]. Row 0 represents 0 items (all zeroes). Column 0 represents 0 capacity (all zeroes).
For item i with weight 2 and value 3: at capacity 5, we compare: 1) Exclude item: dp[i-1][5]. 2) Include item: 3 + dp[i-1][5 - 2] = 3 + dp[i-1][3]. We take the maximum of the two options.
03Space Optimization: Rolling Backward in 1D
Notice that row i depends ONLY on values from row i - 1 at current or smaller capacities (cap and cap - w). Row i - 2 and older are never read again!
Can we collapse the 2D table into a single 1D array int[] dp = new int[W + 1]? YES, but with one critical rule: we MUST iterate the capacity cap backward from W down to w[i-1]! If we iterated forward, dp[cap - w] would already have been updated with the current item, accidentally turning 0/1 Knapsack into Unbounded Knapsack (allowing the same item to be reused multiple times)!
04Why This Matters in Production
Knapsack optimizations drive cloud resource allocation (packing virtual containers into physical server hosts with CPU and RAM limits to minimize cloud hosting bills), financial portfolio asset allocation, and cargo logistics packing.
Understanding the 1D backward iteration pattern allows services to run complex resource optimizations in memory-constrained microservices without allocating multi-megabyte 2D matrix arrays.
05Production Architecture & Engineering Trade-Offs
Dynamic programming solves complex optimization problems by decomposing them into overlapping subproblems and enforcing optimal substructure. However, inexperienced engineers frequently struggle with state-space explosion: defining state dimensions that require excessive memory or state transitions that duplicate computations.
In production applications—such as continuous resource scheduling, query optimization in database planners, and automated financial portfolio rebalancing—space optimization is critical. By recognizing that state transitions often depend only on the immediate previous time step or row, engineers routinely optimize memory consumption from quadratic O(m * n) down to linear O(n) using rolling buffers.
The ideas worth keeping.
- 0/1 Knapsack evaluates binary include/exclude decisions in pseudo-polynomial O(N * W) time.
- Compress 2D knapsack tables to 1D arrays by iterating capacity backward from W down to weight.
- LCS and 2D grid DP problems use similar 2D recurrence relations with rolling row optimizations.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Partition Equal Subset Sum
Explain how determining whether an array can be partitioned into two subsets with equal sum reduces directly to a 0/1 Knapsack problem with target W = sum / 2.
Explore a worked solution
If total sum is odd, return false. Otherwise, find if a subset exists with sum equal to totalSum / 2 using 1D boolean knapsack dp[cap] = dp[cap] || dp[cap - num].Finding a subset summing to half the total means the remaining elements naturally sum to the other half.
Exercise 2: Longest Common Subsequence Formulation
State the recurrence relation for Longest Common Subsequence (LCS) of two strings s1 and s2 at indices i and j.
Explore a worked solution
If s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]. Else: dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]).Matching characters extend the common subsequence by 1; mismatched characters take the best branch excluding either char.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Partition Equal Subset Sum
Explain how determining whether an array can be partitioned into two subsets with equal sum reduces directly to a 0/1 Knapsack problem with target W = sum / 2.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.