0/1 Knapsack with 2D Dynamic Programming

1. What is the 0/1 Knapsack Problem?

Imagine you're a hiker preparing for a trip. You have a knapsack with a specific weight capacity. You also have a set of items, each with its own weight and a value (representing its utility on the trip). Your goal is to choose which items to pack to maximize the total value, without exceeding the knapsack's weight limit.

The "0/1" part is crucial: for each item, you can either take it (1) or leave it (0). You cannot take a fraction of an item.

To get a formal definition and see why this problem is a great candidate for dynamic programming, please watch the first few minutes of the following video.

2. Formulating the DP Solution: State and Recurrence

As we saw in the video, a brute-force approach is too slow. Dynamic programming offers an efficient alternative by breaking the problem into manageable subproblems. To do this, we first need to define our state.

Since our decision for each item depends on which items we've already considered and how much capacity is left, a 2D state is a natural fit.

State: Let dp[i][c] represent the maximum value we can achieve using a subset of the first i items with a knapsack of capacity c.

Our ultimate goal is to find dp[n][capacity], where n is the total number of items.

Now, let's build the recurrence relation. When we consider the i-th item, we have two simple choices:

1. Exclude the i-th item: If we don't pack item i, the maximum value we can get is simply the best we could do with the first i-1 items and the same capacity c.

   • Value = dp[i-1][c]

2. Include the i-th item: We can only do this if the item's weight (wgt[i-1]) is not more than the current capacity c. If we include it, its value (val[i-1]) is added to the maximum value we could get from the first i-1 items with the remaining capacity, c - wgt[i-1].

   • Value = val[i-1] + dp[i-1][c - wgt[i-1]]

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

The following resource provides a very clear, formal derivation of this logic.

So, the formal recurrence relation is:

If wgt[i-1] > c (item i is too heavy):
$dp[i][c]=dp[i-1][c]$

Otherwise:
$dp[i][c]=\max (dp[i-1][c],val[i-1]+dp[i-1][c-wgt[i-1]])$

3. The Tabulation Method: Building the 2D Table

Now we'll use the bottom-up (tabulation) approach to solve this.

1. Create the DP Table: We'll create a 2D array dp of size (n + 1) x (capacity + 1), where n is the number of items.
2. Initialize: The first row (dp[0][...]) and the first column (dp[...][0]) are initialized to 0. This makes sense: if we have 0 items or 0 capacity, the maximum value we can get is 0.
3. Iterate and Fill: We'll use nested loops to fill the table. The outer loop will iterate through the items from i = 1 to n, and the inner loop will iterate through capacities from c = 1 to capacity. Inside the loops, we apply our recurrence relation.

The video from Abdul Bari provides an excellent, detailed walkthrough of filling the table cell by cell.

Here is a Python implementation that directly translates this logic into code.

def knapsack_dp(weights, values, capacity):
    n = len(weights)
    # Initialize dp table with zeros
    # dp[i][c] will store the max value using first i items with capacity c
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # State transition
    for i in range(1, n + 1):
        for c in range(1, capacity + 1):
            # Get weight and value of the current item (i-th item has index i-1)
            weight = weights[i - 1]
            value = values[i - 1]
            
            # Case 1: Current item's weight is more than the capacity 'c'.
            # We cannot include it. So, the max value is the same as the
            # max value without this item.
            if weight > c:
                dp[i][c] = dp[i - 1][c]
            else:
                # Case 2: We have a choice.
                # Option A: Don't include the item. Value is dp[i-1][c].
                # Option B: Include the item. Value is value + dp[i-1][c - weight].
                exclude_item = dp[i - 1][c]
                include_item = value + dp[i - 1][c - weight]
                dp[i][c] = max(exclude_item, include_item)
                
    # The final answer is in the bottom-right cell
    return dp[n][capacity]

# Example usage:
weights = [2, 3, 4, 5]
values = [1, 2, 5, 6]
capacity = 8
max_value = knapsack_dp(weights, values, capacity)
print(f"Maximum value in Knapsack = {max_value}") # Output: 8

4. Reconstructing the Solution

The dp[n][capacity] cell gives us the maximum possible value, but it doesn't tell us which items we chose. To find that, we need to backtrack through our filled DP table.

The logic is simple: starting from the bottom-right cell dp[n][capacity], we retrace our decisions.

1. Start at i = n and c = capacity.
2. Check if dp[i][c] is different from dp[i-1][c].
   • If they are different, it means the i-th item was included in the optimal solution for this state. We add item i to our list and subtract its weight from our current capacity: c = c - wgt[i-1].
   • If they are the same, it means the i-th item was not included.
3. Move up to the previous row (i = i - 1) and repeat until you reach the top of the table.

This last part of the video demonstrates this backtracking process.

You can also find a clean Python implementation of this backtracking logic in the W3Schools article under the section "Which Items Gives Us The Highest Value?".

Conclusion

Congratulations! You've just worked through one of the most fundamental problems in dynamic programming. The 0/1 Knapsack pattern is incredibly versatile and appears in many forms in competitive programming challenges.

Key Takeaways:

• The 0/1 Knapsack problem involves maximizing value within a weight constraint, with an all-or-nothing choice for each item.
• It is solved using a 2D DP table where the state dp[i][c] depends on both the item index i and the remaining capacity c.
• The core recurrence relation comes from making a simple choice for each item: exclude it (dp[i-1][c]) or include it (val[i-1] + dp[i-1][c - wgt[i-1]]).
• After filling the table to find the max value, you can backtrack from the final cell to determine which items were included in the optimal set.

Up Next:
The backtracking we performed to find the items is a specific instance of a powerful, general-purpose algorithmic technique. In our next module, we will dive deep into Backtracking as a standalone topic. You'll learn the general (choose, explore, un-choose) template that can be used to solve a whole new class of problems, such as generating permutations, combinations, and solving puzzles like N-Queens.