0/1 Knapsack Problem

0/1 Knapsack Problem in Dynamic Programming

The 0/1 Knapsack Problem is one of the most famous optimization problems in Computer Science. It perfectly illustrates the power of Dynamic Programming and is a frequent topic in top-tier technical interviews.

1. What is the 0/1 Knapsack Problem?

Imagine you are a thief who has broken into a jewelry store. You have a single knapsack (a bag) that can carry a maximum weight of W.

In the store, there are n items. Each item has:

1. A specific weight (wt).
2. A specific value (val).

Your goal is to steal the optimal combination of items to maximize your total profit, without exceeding the maximum weight limit W of your knapsack.

The "0/1" in the name means you have only two choices for every item:

• 1 (Take it): You put the entire item in your bag.
• 0 (Leave it): You leave the item behind.
• You cannot break an item in half or take a fraction of it.

2. Visualizing the Problem

Let's look at a classic example. Your knapsack can hold exactly 50 kg. There are three items available:

• Item 1: Weighs 10 kg, worth $60.
• Item 2: Weighs 20 kg, worth $100.
• Item 3: Weighs 30 kg, worth $120.

Calculating the possible combinations:

• Item 1 + Item 2: 10kg + 20kg = 30kg. Value: $160.
• Item 1 + Item 3: 10kg + 30kg = 40kg. Value: $180.
• Item 2 + Item 3: 20kg + 30kg = 50kg. Value: $220. (Optimal!)
• All Three: 10kg + 20kg + 30kg = 60kg. (Exceeds 50kg limit, INVALID)

The optimal solution is to take Item 2 and Item 3, achieving a total value of $220.

3. Approaches to Solving 0/1 Knapsack

There are several ways to approach this problem, starting from a naive solution to a highly optimized one.

Approach 1: Brute Force (Recursion)

The simplest way is to evaluate every single possible subset of items. For each item, we branch out into two possibilities: we either include the item in the knapsack, or we exclude it.

• Time Complexity: O(2^n) because we make 2 recursive calls for every item.
• Why it fails: For 50 items, the computer would have to calculate 1,125,899,906,842,624 combinations. It is completely unscalable!

Approach 2: Top-Down Dynamic Programming (Memoization)

In the brute force approach, we end up recalculating the same subproblems repeatedly. We can use a 2D array (cache) to store the results of subproblems as we compute them.

• Time Complexity: O(n * W)
• Space Complexity: O(n * W) for the cache + O(n) for the recursive call stack.

Approach 3: Bottom-Up Dynamic Programming (Tabulation)

This is the industry standard. We build a 2D array from the ground up, avoiding the overhead of deep recursive calls entirely.

4. Understanding Tabulation (The DP Table)

Let's build a DP Table dp[i][w] where:

• i represents the number of items considered so far.
• w represents the current maximum weight capacity of the knapsack.
• The value inside dp[i][w] represents the maximum profit we can achieve.

The Core Logic: For each item i and each weight capacity w, we ask:

1. Is this item heavier than my current capacity w?
   • If yes, I can't take it. My max profit is the same as it was without this item: dp[i-1][w].
2. If I have enough capacity to take it, should I?
   • We compare two scenarios:
     • Scenario A: I take the item. My profit is Item_Value + Profit_of_Remaining_Weight. (val[i-1] + dp[i-1][w-wt[i-1]])
     • Scenario B: I leave the item. My profit is dp[i-1][w].
   • We simply choose the maximum of Scenario A and Scenario B!

5. Python Implementation

Here is the highly optimized Bottom-Up Dynamic Programming approach written in Python.

def knapsack(W, wt, val, n):
    # Create a 2D array filled with 0s. 
    # Rows = n + 1 (items), Cols = W + 1 (weights)
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
    # Build the DP table in a bottom-up manner
    for i in range(n + 1):
        for w in range(W + 1):
            # Base Case: 0 items or 0 weight capacity yields 0 profit
            if i == 0 or w == 0:
                dp[i][w] = 0
            # If item weight is less than or equal to current capacity
            elif wt[i-1] <= w:
                # Max of: (Value of current item + Value of remaining weight) OR (Value without current item)
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]],  dp[i-1][w])
            # If item weight is greater than current capacity, we cannot take it
            else:
                dp[i][w] = dp[i-1][w]
    # The bottom-right cell contains the maximum profit
    return dp[n][W]

# Given inputs from our visual example
values = [60, 100, 120]
weights = [10, 20, 30]
max_weight = 50
n_items = len(values)
max_profit = knapsack(max_weight, weights, values, n_items)
print(f"The Maximum profit is: ${max_profit}")

6. Time and Space Complexity

• Time Complexity: O(N * W) where N is the total number of items and W is the maximum capacity of the knapsack. The nested for loops iterate strictly N times and W times.
• Space Complexity: O(N * W). We require a 2D array of size (N+1) * (W+1) to store the intermediate subproblem results. (Note: Space complexity can be further optimized to O(W) using only a 1D array since we only ever look back at the previous row).