Solving 0/1 Knapsack with DP

Welcome back! In our last lesson, we established a blueprint for converting recursive, memoized DP solutions into iterative, bottom-up ones. You learned that both approaches solve the same subproblems, but tabulation does so by systematically building up from the base cases, often leading to better performance.

Today, we'll apply this knowledge to one of the most famous problems in computer science: the 0/1 Knapsack problem. This problem serves as a gateway to 2D dynamic programming and is a powerful pattern for solving a wide range of resource allocation puzzles. Given your interest in finance, you can think of it as a simplified model of portfolio construction: you have a limited budget (the knapsack's capacity) and a set of potential investments (items), each with a cost (weight) and an expected return (value). Your goal is to choose the combination of investments that maximizes your total return without exceeding your budget.

Our objective is to formulate the recurrence relation for the 0/1 knapsack problem and then implement a solution using a 2D DP table, solidifying the bottom-up approach we studied previously.

Understanding the 0/1 Knapsack Problem

The problem is defined as follows: you are given a set of items, each with a specific weight and value. You also have a knapsack that can hold a certain maximum weight. Your task is to select a subset of these items to put into the knapsack such that the total value of the selected items is maximized, and their total weight does not exceed the knapsack's capacity. The "0/1" constraint means that for each item, you have two choices: either you take the whole item (1) or you leave it behind (0). You cannot take a fraction of an item.

The following resource provides a clear and structured introduction to the problem.

Like the problems we've seen before, the 0/1 Knapsack problem exhibits the two key properties that make it suitable for dynamic programming:

1. Optimal Substructure: The optimal solution to the problem (for n items and capacity W) contains within it the optimal solutions to smaller subproblems (e.g., for n-1 items).
2. Overlapping Subproblems: A naive recursive approach would repeatedly solve the same subproblems. For example, the maximum value for the first 3 items with a remaining capacity of 10 might be needed in many different decision paths.

Formulating the Recurrence Relation

To solve this with DP, we first need to define the state and the recurrence relation. This is the most crucial part of solving any DP problem. We'll follow the structured thinking from our last lesson.

1. Define the State

At any point, what information do we need to make a decision? We need to know which item we are currently considering and how much capacity we have left in the knapsack. This leads to a two-dimensional state: (i, c), representing the subproblem of finding the maximum value using only the first i items with a knapsack of capacity c.

Let's define dp[i][c] as the solution to this subproblem. Our goal is to find dp[n][W], where n is the total number of items and W is the total capacity of the knapsack.

2. Define the Choices

For each item i, we face a decision with two possible outcomes:

• Choice A: Do not include item i in the knapsack.
  If we don't take item i, then the maximum value we can get is simply the best we could do with the previous i-1 items, using the same capacity c. The value for this choice is dp[i-1][c].

• Choice B: Include item i in the knapsack.
  We can only make this choice if the weight of item i (wgt[i-1]) is less than or equal to the current capacity c. If we take it, we gain its value (val[i-1]), but we use up wgt[i-1] of our capacity. The remaining value must come from the optimal solution for the first i-1 items with the reduced capacity c - wgt[i-1]. The value for this choice is val[i-1] + dp[i-1][c - wgt[i-1]].

3. The Recurrence Relation

Since we want to maximize the value, we simply take the maximum of these two choices. This gives us our state transition equation.

The resource from Hello Algo walks through this derivation beautifully.

So, the full recurrence relation is:

• If wgt[i-1] > c (item i is too heavy):
  $dp[i][c]=dp[i-1][c]$
• If wgt[i-1] <= c:
  $dp[i][c]=\max (dp[i-1][c],val[i-1]+dp[i-1][c-wgt[i-1]])$

Bottom-Up Implementation with a 2D Table

Now, let's build the solution iteratively using a 2D DP table. This process will feel very familiar from our last lesson, but now applied to a 2D state.

1. Create the DP Table: Our state (i, c) has two parameters. We'll use a 2D array, let's call it dp, of size (n+1) x (W+1), where n is the number of items and W is the knapsack capacity. dp[i][j] will store the max value using the first i items with capacity j.

2. Initialize Base Cases: The "Hello Algo" resource mentions this in Step 3. When there are no items (i=0) or the capacity is zero (c=0), the maximum value is 0. This means the entire first row (dp[0][c]) and the entire first column (dp[i][0]) of our table should be initialized to 0. Most programming languages will default-initialize a new integer array to zeros, so this is often handled for us.

3. Iterate and Apply Recurrence: Our recurrence dp[i][c] depends on values in the previous row (i-1). This tells us our outer loop must iterate over the items, and the inner loop over the capacities.

   • Outer loop for i from 1 to n.
   • Inner loop for c from 1 to W.
   • Inside the loops, we implement the if/else logic of our recurrence relation.

The following video provides an exceptionally clear, step-by-step walkthrough of filling this 2D table. It masterfully explains the meaning of each cell as the answer to a specific subproblem, which is key to demystifying the process.

Here is a clean Python implementation that matches the logic we've just discussed. The final answer is the value in the bottom-right corner of the dp table.

The image below shows an example of a filled DP table. The arrows illustrate how the value in a cell is derived from values in the previous row, corresponding to the "don't take" and "take" decisions.

Complexity Analysis

• Time Complexity: We are filling a 2D table of size (n+1) x (W+1). Since we perform a constant amount of work for each cell, the total time complexity is O(n * W).
• Space Complexity: We need to store the entire 2D table, so the space complexity is also O(n * W).

An interesting point for a CS major: this complexity is called pseudo-polynomial. The runtime depends not just on the number of items n, but on the magnitude of the capacity W. If W is extremely large (e.g., 2^n), the algorithm's runtime can become exponential relative to the size of the input representation.

Conclusion

In this lesson, we tackled the classic 0/1 Knapsack problem. By applying the DP principles from our previous sessions, you learned how to handle a problem with a two-dimensional state, a common pattern in more advanced DP challenges.

Key Takeaways:

• Problem Definition: The 0/1 Knapsack problem asks for the maximum value of items that can fit into a weight-constrained bag, where items are indivisible.
• State Formulation: The problem requires a 2D state, dp[i][c], representing the maximum value achievable with the first i items and a capacity of c.
• Recurrence Relation: The core logic lies in the choice for each item: either we don't take it (dp[i-1][c]) or we take it (val[i-1] + dp[i-1][c - wgt[i-1]]). The DP state is the maximum of these two options.
• 2D Table Implementation: A bottom-up solution involves iterating through items and capacities to fill an (n+1) x (W+1) table, with the final answer located at dp[n][W].

The O(n * W) space complexity of our solution is correct, but for interviews, it's often expected that you can do better. In our next lesson, we will explore a common and clever optimization that reduces the space complexity of the 0/1 Knapsack solution to just O(W), a significant improvement. This technique relies on a careful analysis of the data dependencies within the DP table.