0/1 Knapsack Problem: Dynamic Programming Deep Dive with Java
Resource allocation is one of the most common problems in software engineering, and it shows up in more places than you'd expect. Budget planning tools, cloud VM packing, cargo loading systems, ad auction bidding, even compiler register allocation — all of these are flavors of the same underlying problem: given a fixed budget of some resource, which items do you pick to squeeze out maximum value? The 0/1 Knapsack Problem is the canonical formulation of this class of challenge, and mastering it gives you a mental template you'll reuse constantly.
The naive recursive approach explodes into O(2ⁿ) time because every item forces a binary branch — take it or leave it — and those branches multiply exponentially. Dynamic Programming tames this by recognizing that subproblems overlap: the best way to fill a 7kg bag from items 1–4 gets computed dozens of times in the recursive tree. DP caches each unique subproblem result so it's solved exactly once, collapsing exponential work into a polynomial O(n × W) solution.
By the end of this article you'll understand not just the DP table mechanics but why each cell means what it means, how to reconstruct which items were actually chosen (not just the max value), how to reduce space from O(n × W) to O(W) without losing correctness, and the subtle edge cases that cause silent wrong answers in production code. You'll also be ready for the three hardest interview questions that trip people up even after they've memorized the algorithm.
Building the DP Table From First Principles — What Each Cell Actually Means
Before writing a single line of code, you need a rock-solid mental model of the DP table. Define dp[i][w] as: the maximum value achievable using exactly the first i items, with a weight capacity of exactly w kilograms. That 'first i items' framing is deliberate — it lets us shrink the problem one item at a time.
The recurrence has two cases. If item i is heavier than the current capacity w, we simply can't include it, so dp[i][w] = dp[i-1][w] — inherit the best answer without that item. If the item fits, we have a choice: skip it (dp[i-1][w]) or take it (dp[i-1][w - weight[i]] + value[i]). We take the max of those two options. That's the entire algorithm — two lines of logic that, when applied systematically across an (n+1) × (W+1) table, produce the globally optimal answer.
The base cases matter: dp[0][w] = 0 for all w (no items means no value) and dp[i][0] = 0 for all i (zero capacity means you can carry nothing). Java initializes int arrays to zero, which handles both base cases for free — but only if you size the array correctly as (n+1) × (W+1).
public class KnapsackDP { /** * Solves the 0/1 Knapsack problem using a full 2D DP table. * * @param itemWeights weight of each item (index 0-based) * @param itemValues value of each item (index 0-based) * @param maxCapacity maximum weight the knapsack can hold * @return maximum total value achievable */ public static int solve(int[] itemWeights, int[] itemValues, int maxCapacity) { int itemCount = itemWeights.length; // dp[i][w] = best value using first i items with capacity w // Size is (itemCount+1) x (maxCapacity+1) so index 0 represents "no items" / "no capacity" int[][] dp = new int[itemCount + 1][maxCapacity + 1]; for (int i = 1; i <= itemCount; i++) { // Shift to 0-based index for the item arrays int currentWeight = itemWeights[i - 1]; int currentValue = itemValues[i - 1]; for (int capacity = 0; capacity <= maxCapacity; capacity++) { // Case 1: current item is too heavy to fit — skip it if (currentWeight > capacity) { dp[i][capacity] = dp[i - 1][capacity]; } else { // Case 2: choose the better option — skip or take int valueIfSkipped = dp[i - 1][capacity]; int valueIfTaken = dp[i - 1][capacity - currentWeight] + currentValue; dp[i][capacity] = Math.max(valueIfSkipped, valueIfTaken); } } } // Print the full DP table so we can trace the logic System.out.println("DP Table (rows=items 0.." + itemCount + ", cols=capacity 0.." + maxCapacity + "):"); for (int i = 0; i <= itemCount; i++) { for (int w = 0; w <= maxCapacity; w++) { System.out.printf("%4d", dp[i][w]); } System.out.println(); } return dp[itemCount][maxCapacity]; } public static void main(String[] args) { // A courier has a bag with 7kg capacity. // Items: (weight, value) — laptop bag(3,4), camera(4,5), tripod(2,3), books(1,1) int[] weights = {3, 4, 2, 1}; int[] values = {4, 5, 3, 1}; int capacity = 7; int maxValue = solve(weights, values, capacity); System.out.println("\nMax value achievable: " + maxValue); } }
0 0 0 0 0 0 0 0
0 0 0 4 4 4 4 4
0 0 0 4 5 5 5 9
0 0 3 4 5 7 8 9
0 1 3 4 5 7 8 9
Max value achievable: 9
Reconstructing the Chosen Items — Tracing Back Through the DP Table
Most resources stop at returning the max value. But in any real system — a cargo packing tool, a portfolio optimizer, a procurement system — you need to know which items to actually pack. Value alone is useless without the item list.
The reconstruction trick is elegant: once the DP table is built, start at dp[n][W] (the answer cell) and walk backwards. At row i, capacity w — if dp[i][w] != dp[i-1][w], item i was included in the optimal solution. Subtract its weight from the current capacity and move to row i-1. If they're equal, item i was skipped — just move up to row i-1 with the same capacity.
This works because the recurrence guarantees that whenever we took an item, the cell value differs from the row above. When we skipped an item, the value propagates unchanged from the row above. You're essentially reverse-engineering the decisions stored in the table.
One gotcha: if multiple items have the same weight and value, there may be multiple valid optimal selections. The backtracking gives you one valid solution, not all of them. If you need all solutions, you'd need a different enumeration approach — keep that in mind for interview follow-ups.
import java.util.ArrayList; import java.util.List; public class KnapsackWithItemTracking { static class Item { String name; int weight; int value; Item(String name, int weight, int value) { this.name = name; this.weight = weight; this.value = value; } @Override public String toString() { return name + "(w=" + weight + ", v=" + value + ")"; } } static class KnapsackResult { int maxValue; List<Item> chosenItems; KnapsackResult(int maxValue, List<Item> chosenItems) { this.maxValue = maxValue; this.chosenItems = chosenItems; } } public static KnapsackResult solve(List<Item> items, int maxCapacity) { int n = items.size(); // Build the full DP table — we need every cell for backtracking int[][] dp = new int[n + 1][maxCapacity + 1]; for (int i = 1; i <= n; i++) { Item current = items.get(i - 1); for (int capacity = 0; capacity <= maxCapacity; capacity++) { // Default: don't take current item dp[i][capacity] = dp[i - 1][capacity]; // Check if taking it would be better if (current.weight <= capacity) { int valueIfTaken = dp[i - 1][capacity - current.weight] + current.value; if (valueIfTaken > dp[i][capacity]) { dp[i][capacity] = valueIfTaken; } } } } // --- Backtrack to find which items were chosen --- List<Item> chosen = new ArrayList<>(); int remaining = maxCapacity; for (int i = n; i >= 1; i--) { // If this row's value differs from the row above, item i was taken if (dp[i][remaining] != dp[i - 1][remaining]) { Item takenItem = items.get(i - 1); chosen.add(0, takenItem); // prepend to maintain original order remaining -= takenItem.weight; // reduce remaining capacity } // If values match, item i was skipped — just move up a row } return new KnapsackResult(dp[n][maxCapacity], chosen); } public static void main(String[] args) { List<Item> inventory = new ArrayList<>(); inventory.add(new Item("LaptopBag", 3, 4)); inventory.add(new Item("Camera", 4, 5)); inventory.add(new Item("Tripod", 2, 3)); inventory.add(new Item("Books", 1, 1)); int capacity = 7; KnapsackResult result = solve(inventory, capacity); System.out.println("Max value: " + result.maxValue); System.out.println("Items chosen:"); int totalWeight = 0; for (Item item : result.chosenItems) { System.out.println(" -> " + item); totalWeight += item.weight; } System.out.println("Total weight used: " + totalWeight + " / " + capacity); } }
Items chosen:
-> LaptopBag(w=3, v=4)
-> Camera(w=4, v=5)
Total weight used: 7 / 7
Space Optimization: Collapsing the DP Table to a Single Row (O(W) Space)
The 2D DP table uses O(n × W) space. For n=1000 items and W=100,000, that's 100 million integers — roughly 400MB. That's a problem. Fortunately, the recurrence only ever looks at the previous row (dp[i-1][...]) to compute the current row (dp[i][...]). That means you only need to keep two rows at once — or with one critical trick, just one row.
The trick: iterate the capacity loop right-to-left when using a single 1D array. Here's why this matters deeply. In the 2D version, dp[i][w] reads from dp[i-1][w - weight], which is in the previous row — guaranteed to not yet be overwritten. In a 1D array where we reuse the same row, if we iterate left-to-right, we'd overwrite dp[w - weight] before reading it, effectively allowing the same item to be picked twice (turning it into an unbounded knapsack). Iterating right-to-left ensures that when we read dp[capacity - weight], that value still reflects the state before the current item was considered.
This is a subtle but critical correctness constraint. The right-to-left iteration is not an optimization trick — it's a correctness requirement specific to 0/1 (as opposed to unbounded) knapsack.
public class KnapsackSpaceOptimized { /** * Solves 0/1 Knapsack with O(W) space using a single 1D DP array. * * CRITICAL: capacity loop MUST run right-to-left to prevent * counting the same item more than once. */ public static int solve(int[] itemWeights, int[] itemValues, int maxCapacity) { int itemCount = itemWeights.length; // Single row: dp[w] = best value achievable with capacity w // considering items processed so far int[] dp = new int[maxCapacity + 1]; for (int i = 0; i < itemCount; i++) { int weight = itemWeights[i]; int value = itemValues[i]; // RIGHT-TO-LEFT: ensures dp[capacity - weight] still reflects // the state BEFORE item i was considered. // Left-to-right would let us 'use' item i multiple times — wrong! for (int capacity = maxCapacity; capacity >= weight; capacity--) { int valueIfTaken = dp[capacity - weight] + value; int valueIfSkipped = dp[capacity]; // Only update if taking the item is strictly better dp[capacity] = Math.max(valueIfTaken, valueIfSkipped); } // Show state of dp array after processing each item System.out.print("After item " + i + " (w=" + weight + ", v=" + value + "): "); for (int w = 0; w <= maxCapacity; w++) { System.out.printf("%3d", dp[w]); } System.out.println(); } return dp[maxCapacity]; } public static void main(String[] args) { int[] weights = {3, 4, 2, 1}; int[] values = {4, 5, 3, 1}; int capacity = 7; int result = solve(weights, values, capacity); System.out.println("\nMax value (space-optimized): " + result); // Demonstrate the bug that RIGHT-TO-LEFT prevents: // If we ran left-to-right with item weight=2, value=3, capacity=6: // dp[2] gets updated first, then dp[4] = dp[2]+3 uses the NEW dp[2], // effectively using the item twice. Right-to-left prevents this. System.out.println("\n--- Demonstrating left-to-right BUG on unbounded behavior ---"); demonstrateBug(new int[]{2}, new int[]{3}, 6); } // Shows what goes wrong if you iterate left-to-right (treating it as unbounded knapsack) static void demonstrateBug(int[] itemWeights, int[] itemValues, int maxCapacity) { int[] dpBuggy = new int[maxCapacity + 1]; int[] dpCorrect = new int[maxCapacity + 1]; int w = itemWeights[0], v = itemValues[0]; // Buggy: left-to-right (item gets reused) for (int capacity = w; capacity <= maxCapacity; capacity++) { dpBuggy[capacity] = Math.max(dpBuggy[capacity], dpBuggy[capacity - w] + v); } // Correct: right-to-left (item used at most once) for (int capacity = maxCapacity; capacity >= w; capacity--) { dpCorrect[capacity] = Math.max(dpCorrect[capacity], dpCorrect[capacity - w] + v); } System.out.println("Left-to-right (buggy, unbounded): dp[6] = " + dpBuggy[6] + " (item used " + (dpBuggy[6]/v) + " times)"); System.out.println("Right-to-left (correct, 0/1): dp[6] = " + dpCorrect[6] + " (item used " + (dpCorrect[6]/v) + " time)"); } }
After item 1 (w=4, v=5): 0 0 0 4 5 5 7 9
After item 2 (w=2, v=3): 0 0 3 4 5 7 8 9
After item 3 (w=1, v=1): 0 1 3 4 5 7 8 9
Max value (space-optimized): 9
--- Demonstrating left-to-right BUG on unbounded behavior ---
Left-to-right (buggy, unbounded): dp[6] = 9 (item used 3 times)
Right-to-left (correct, 0/1): dp[6] = 3 (item used 1 time)
Edge Cases, Performance Ceilings, and When DP Falls Apart in Production
The O(n × W) complexity looks polynomial, but W is the numeric value of the capacity, not the number of bits needed to represent it. This is called pseudo-polynomial time. If W = 10^9, you'd need a 10^9-column array — completely infeasible. This matters deeply in practice: never assume the DP approach is tractable without bounding W first.
For large W with small n, meet-in-the-middle (split items into two halves, enumerate all 2^(n/2) subsets of each, then binary search for complement pairs) becomes practical. For fractional variants, greedy by value-to-weight ratio is optimal. For W beyond practical DP limits but n small enough, branch-and-bound with good pruning often beats brute force significantly.
Edge cases that cause silent wrong answers: items with zero weight (they're always free — handle them separately or they'll trivially dominate), items heavier than total capacity (the condition weight <= capacity in the inner loop correctly handles this, but if you invert the condition you'll corrupt the table), and integer overflow when item values are large and you sum many of them. Use long instead of int when item values could exceed ~200,000 with 20+ items. Also validate that all weights and values are non-negative — negative values break the recurrence's optimality guarantee entirely.
import java.util.Arrays; public class KnapsackEdgeCases { /** * Production-hardened 0/1 Knapsack — handles edge cases explicitly: * - Zero-weight items (always include them — they're free value) * - Items heavier than total capacity (silently skipped) * - Large values that risk integer overflow (uses long) * - Empty item list or zero capacity */ public static long solve(int[] itemWeights, long[] itemValues, int maxCapacity) { // Guard: trivial cases if (itemWeights == null || itemValues == null || itemWeights.length == 0 || maxCapacity <= 0) { return 0L; } if (itemWeights.length != itemValues.length) { throw new IllegalArgumentException( "weights and values arrays must have the same length"); } int itemCount = itemWeights.length; long freeValue = 0L; // sum of zero-weight items — always take these // Separate zero-weight items — they're always optimal to include // Including them in the DP loop causes incorrect table indexing for (int i = 0; i < itemCount; i++) { if (itemWeights[i] < 0 || itemValues[i] < 0) { throw new IllegalArgumentException( "Negative weights/values not supported — recurrence breaks"); } if (itemWeights[i] == 0) { freeValue += itemValues[i]; // take all zero-weight items } } // Space-optimized 1D DP using long to prevent overflow long[] dp = new long[maxCapacity + 1]; Arrays.fill(dp, 0L); for (int i = 0; i < itemCount; i++) { int weight = itemWeights[i]; long value = itemValues[i]; if (weight == 0) continue; // already handled above // Items heavier than maxCapacity are silently skipped — // the loop condition `capacity >= weight` never fires for them for (int capacity = maxCapacity; capacity >= weight; capacity--) { long valueIfTaken = dp[capacity - weight] + value; if (valueIfTaken > dp[capacity]) { dp[capacity] = valueIfTaken; } } } long result = dp[maxCapacity] + freeValue; System.out.println("DP result: " + dp[maxCapacity] + ", Free value from zero-weight items: " + freeValue + ", Total: " + result); return result; } public static void main(String[] args) { System.out.println("=== Test 1: Normal case ==="); solve(new int[]{3, 4, 2, 1}, new long[]{4, 5, 3, 1}, 7); System.out.println("\n=== Test 2: Zero-weight item present ==="); // Item weight=0 value=100 should ALWAYS be included (it's free!) solve(new int[]{3, 0, 2}, new long[]{4, 100, 3}, 5); System.out.println("\n=== Test 3: All items heavier than capacity ==="); // Every item weighs 10 but capacity is 5 — result must be 0 solve(new int[]{10, 10, 10}, new long[]{50, 60, 70}, 5); System.out.println("\n=== Test 4: Large values testing overflow safety ==="); // Values near Integer.MAX_VALUE — using long prevents corruption solve(new int[]{1, 1, 1}, new long[]{2_000_000_000L, 2_000_000_000L, 2_000_000_000L}, 3); System.out.println("\n=== Test 5: Empty items ==="); long empty = solve(new int[]{}, new long[]{}, 10); System.out.println("Empty result: " + empty); } }
DP result: 9, Free value from zero-weight items: 0, Total: 9
=== Test 2: Zero-weight item present ===
DP result: 7, Free value from zero-weight items: 100, Total: 107
=== Test 3: All items heavier than capacity ===
DP result: 0, Free value from zero-weight items: 0, Total: 0
=== Test 4: Large values testing overflow safety ===
DP result: 6000000000, Free value from zero-weight items: 0, Total: 6000000000
=== Test 5: Empty items ===
Empty result: 0
| Aspect | 2D DP Table (n × W) | 1D Space-Optimized DP |
|---|---|---|
| Time Complexity | O(n × W) | O(n × W) |
| Space Complexity | O(n × W) | O(W) |
| Item Reconstruction | Yes — backtrack through full table | No — table overwritten each row |
| Code Complexity | Moderate — two index offsets to manage | Simpler loop, but iteration direction is critical |
| When to Use | When you need to know WHICH items were chosen | When you only need the max value and memory is tight |
| Risk of Silent Bug | Low — row isolation prevents cross-contamination | High — left-to-right iteration silently becomes unbounded knapsack |
| Overflow Risk | High with int and large values — use long | Same — use long when item values are large |
| Large W Feasibility | Infeasible at W > ~10^7 (memory explosion) | Feasible slightly higher but still pseudo-polynomial |
🎯 Key Takeaways
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Sizing the DP array as [n][W] instead of [n+1][W+1] — Symptom: ArrayIndexOutOfBoundsException or dp[0][...] base cases overwriting real item rows — Fix: Always allocate (n+1) rows and (W+1) columns so row 0 and column 0 cleanly represent the 'no items' and 'zero capacity' base cases without conflicting with actual item data.
- ✕Mistake 2: Iterating left-to-right in the 1D space-optimized version — Symptom: No exception, no crash — just wrong answers that are suspiciously high because items are counted multiple times (it silently becomes unbounded knapsack) — Fix: Always iterate the capacity loop from maxCapacity down to itemWeight when using a 1D array for 0/1 knapsack. Commit this rule to memory: right-to-left = 0/1, left-to-right = unbounded.
- ✕Mistake 3: Using int instead of long for item values — Symptom: Negative or wildly incorrect max value returned when individual values are large (e.g., >10^8) and multiple items are selected, due to silent integer overflow — Fix: Declare the DP array and value arrays as long. Java silently wraps int overflow with no warning, so this bug can survive testing if your test cases happen to use small values.
Interview Questions on This Topic
- QCan you solve 0/1 Knapsack in true polynomial time? Why or why not — and what does pseudo-polynomial mean in this context?
- QHow would you modify the 0/1 Knapsack DP to handle the case where each item can be taken at most k times (bounded knapsack), without just duplicating items k times in the input array?
- QYou've optimized the knapsack to O(W) space using a 1D array. Your tech lead now asks you to also return the list of items that make up the optimal solution. What do you do — and what's the minimum additional space needed?
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.