01 Knapsack Problem DP Java | Fresher Interview
Fast recall
Quick revision
Core answer
dp[i][w] = max value using the first i items with capacity w. For each item, choose the better of skip (dp[i-1][w]) or take (dp[i-1][w - wt] + val, if it fits). O(n*W) time; reducible to O(W) space by iterating weight backwards.Whether you set up the take/skip transition and know the 0/1 (each item once) constraint and backward 1D optimization
Allowing item reuse (that's unbounded knapsack), or iterating weight forward in the 1D version (which reuses items)
Explain why the 1D rolling array must iterate weight in reverse to enforce 'each item once'
Interview-ready guide
Interview answer
In the zero-one knapsack problem, I have a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity.
Each item can either be taken once or left out entirely, no fractions and no repeats, and I want to maximize the total value without exceeding the capacity. I define dp of i, w as the maximum value I can achieve using the first i items with a capacity of w. For each item, I have two choices.
I can skip it, in which case the value is dp of i minus one, w, the best I could do with the previous items and the same capacity. Or, if the item fits, I can take it, which gives its value plus dp of i minus one, w minus the item's weight, the best I could do with the remaining capacity using the earlier items.
I take the maximum of those two. The base case is zero items giving zero value. The full two-dimensional table is O of n times W in both time and space.
A nice optimization is to collapse it to a one-dimensional array indexed by weight, but there's a critical detail: I have to iterate the weight from high to low, backwards. If I went forward, then dp of w minus the weight would already reflect the current item, which would effectively let me use the same item multiple times, and that turns it into the unbounded knapsack problem.
Iterating backward keeps dp of w minus weight referring to the previous item's state, correctly enforcing the take-each-item-once rule. I'd also distinguish this from fractional knapsack, where you can take fractions of items, which is solved greedily by value-to-weight ratio rather than with DP.
01 Knapsack Problem DP Java | Fresher Interview
Direct Answer
0/1 knapsack: pick items (each used at most once) to maximize value within a weight capacity. dp[i][w] = max value using the first i items with capacity w. For each item, choose the better of skip (dp[i-1][w]) or take (dp[i-1][w - wt] + val, if it fits). O(n*W) time; reducible to O(W) space by iterating weight backwards.
Deep Dive & Architecture
For every item and capacity, there are only two valid choices. Skip the item and keep the value already known for that capacity, or take it—if it fits—and add its value to the best result for the remaining capacity.
In a two-dimensional table, row i uses only row i - 1, which guarantees that one item is never selected twice. The same idea can use one array when capacities are visited from high to low.
Worked example
For weights [1, 3, 4, 5], values [1, 4, 5, 7], and capacity 7, item weight 3 can combine with item weight 4. Their total weight is 7 and value is 9. Weight 5 plus weight 1 gives value 8, so the table keeps 9.
The backward loop is essential. While processing the weight-3 item, dp[7] reads dp[4] from the previous item state. A forward loop could read a value that already includes the same item and would silently turn the problem into unbounded knapsack.
With n items and capacity W, the algorithm takes O(nW) time. The one-dimensional version uses O(W) space. This is pseudo-polynomial because it depends on the numeric capacity, not only on the number of input items.
Code Example
int knapsack(int[] wt, int[] val, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < wt.length; i++)
for (int w = W; w >= wt[i]; w--) // BACKWARD: each item once
dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
return dp[W];
}
// wt={1,3,4,5}, val={1,4,5,7}, W=7
// best = items {weight3,weight4} -> value 4+5 = 9 -> dp[7]=9
Iterating w downward ensures dp[w - wt[i]] still refers to the previous item row.
Common Mistakes & Pitfalls
- Allowing reuse: taking an item multiple times is unbounded knapsack, a different problem.
- Forward 1D loop: iterating
wascending in the 1D version reuses the same item - must go backward. - Fractional items: 0/1 forbids fractions (that's fractional knapsack, solved greedily).
- Off-by-one on capacity: only
takewhenweight[i] <= w.
Check your understanding
Answer these without looking back at the article.
- What is dynamic programming and when do you use it?
- What is memoization vs tabulation in DP and which should you use in interviews?
- How do you solve the coin change problem using dynamic programming?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.