0 - 1 Knapsack Problem - Optimized Solution

Optimized solution

In the previous problem’s solution, if we observe carefully, we can see that the dp solution with states (i, j) will depend on the state (i-1, j) or (i-1, j-wt[i-1]). In either case, the solution for the state (i, j) will lie in the i - 1 row of the memoization table. So at every iteration of the index, we can copy the values of the current row and use only this row for building the solution in the next iteration and no other row will be used. Hence, at any iteration, we will be using only a single row to build the solution for the current row. This is how we can reduce the space complexity to just ${O(W)}$.

Let’s look at the implementation now.