0/1 Knapsack with Dynamic Programming

1. What is the 0/1 Knapsack Problem?

Imagine you're a thief with a knapsack. You have a collection of items, each with a specific weight and profit. Your knapsack has a maximum weight capacity. Your goal is to choose which items to put in the knapsack to maximize your total profit, without exceeding the weight limit.

The "0/1" part is crucial: for each item, you have only two choices. You either take the entire item (1) or leave it behind (0). You cannot take a fraction of an item.

Let's watch a short video to get a clear definition of the problem.

As the video mentions, a simple greedy strategy (like picking items with the highest profit-to-weight ratio first) does not guarantee an optimal solution for the 0/1 Knapsack problem. This is because a high-ratio item might take up weight in a way that prevents you from picking other, more valuable combinations. This is exactly the kind of optimization problem where Dynamic Programming shines.

2. The Path to a DP Solution: From Recursion to Memoization

As we learned previously, the first step towards a DP solution is often to formulate a plain recursive solution. For each item, we face a decision:

1. Include the item: We can only do this if its weight is less than or equal to the remaining capacity of the knapsack. If we include it, we get its profit, and the knapsack's remaining capacity decreases.
2. Exclude the item: We simply move on to the next item without any change in profit or capacity.

The optimal solution will be the maximum of the profits from these two choices.

This logic gives us a recursive structure. A function knapSack(capacity, weights, profits, n) would represent the maximum profit we can get from the first n items with a given capacity.

This recursive solution has a time complexity of $O(2^N)$ because it re-computes the same subproblems repeatedly. Just like with Fibonacci, we can optimize this by storing the results of subproblems. Since our state is defined by two variables (the number of items considered, n, and the remaining capacity, W), we'll need a 2D array for memoization.

By memoizing, we reduce the time complexity to $O(N\times W)$, where N is the number of items and W is the knapsack capacity. The space complexity is also $O(N\times W)$ for the dp table, plus the recursion stack space.

3. The Tabulated Solution (Bottom-Up DP)

Now, let's build the solution iteratively, which is the main goal for today. We'll create a 2D table (or matrix) to store the optimal profits for all subproblems.

• Let dp[i][w] be the maximum profit we can achieve using the first i items with a knapsack of capacity w.
• Our table will have N+1 rows (for items 0 to N) and W+1 columns (for capacities 0 to W).

The recurrence relation we will use to fill each cell dp[i][w] is:

• If the weight of the i-th item (wt[i-1]) is greater than the current capacity w, we cannot include it. So, the profit is the same as the profit without this item: dp[i][w] = dp[i-1][w].
• Otherwise, we choose the maximum of:
  1. Excluding the item: dp[i-1][w]
  2. Including the item: profits[i-1] + dp[i-1][w - wt[i-1]]

The final answer will be in the bottom-right cell of the table, dp[N][W].

Watching this process is the best way to understand it.

Now that you've seen the process, let's look at the complete Java implementation for the tabulation method.

4. Backtracking to Find the Items

The DP table gives us the maximum profit, but it doesn't immediately tell us which items we selected. To find the combination of items, we can backtrack from the final cell dp[N][W].

The logic is simple:

1. Start at dp[i][w] = dp[N][W].
2. Compare dp[i][w] with dp[i-1][w].
3. If they are the same, it means the i-th item was not included. We move up to dp[i-1][w].
4. If they are different, it means the i-th item was included. We add this item to our solution set, subtract its profit and weight, and move to dp[i-1][w - wt[i-1]].
5. Repeat until i or w becomes 0.

The Abdul Bari video you watched earlier also demonstrates this process.

5. Space Optimization (An Interview Bonus)

For your interview preparation, it's great to know that this solution can be space-optimized. Notice that to compute any cell in row i, we only need information from the previous row, i-1. We don't need all N previous rows.

This allows us to reduce the space complexity from $O(N\times W)$ to just $O(W)$ by using a 1D array. This is a common and impressive optimization to discuss in an interview.

Conclusion

Congratulations on tackling your first 2D DP problem! The 0/1 Knapsack is a foundational algorithm, and the patterns you learned today are applicable to a wide variety of other problems.

Key Takeaways:

• The 0/1 Knapsack problem seeks to maximize profit within a weight constraint for indivisible items.
• It's a classic 2D DP problem because its state is defined by two variables: the item index and the remaining knapsack capacity.
• The core of the DP solution is the recurrence relation that decides whether to include or exclude an item at each step.
• The tabulated (bottom-up) solution builds a 2D table iteratively, solving smaller subproblems first. Its time complexity is $O(N\times W)$.
• We can backtrack through the completed DP table to find which items were chosen.
• The solution can be space-optimized from $O(N\times W)$ to $O(W)$.

Preview of the Next Lesson:
We will continue practicing 2D dynamic programming by solving another classic problem: finding the Longest Common Subsequence (LCS). This problem has a slightly different structure but reinforces the core concepts of building a 2D DP table to find an optimal solution.