0/1 Knapsack Problem [DP]

Python Java C++

def knapsack(values, weights, capacity):
    n = len(values)
    # Initialize dp array
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # Build solution for each item and capacity
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                withItem = values[i-1] + dp[i-1][w-weights[i-1]]
                withoutItem = dp[i-1][w]
                dp[i][w] = max(withItem, withoutItem)
            else:
                dp[i][w] = dp[i-1][w]
                
    return dp[n][capacity]

class Solution {
    public int knapsack(int[] values, int[] weights, int capacity) {
        int n = values.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        for (int i = 1; i <= n; i++)
            for (int w = 0; w <= capacity; w++)
                if (weights[i-1] <= w) {
                    int withItem = values[i-1] + dp[i-1][w-weights[i-1]];
                    int withoutItem = dp[i-1][w];
                    dp[i][w] = Math.max(withItem, withoutItem);
                } else {
                    dp[i][w] = dp[i-1][w];
                }
        
        return dp[n][capacity];
    }
}

class Solution {
public:
    int knapsack(vector& values, vector& weights, int capacity) {
        int n = values.size();
        vector> dp(n + 1, vector(capacity + 1, 0));
        
        for (int i = 1; i <= n; i++)
            for (int w = 0; w <= capacity; w++)
                if (weights[i-1] <= w) {
                    int withItem = values[i-1] + dp[i-1][w-weights[i-1]];
                    int withoutItem = dp[i-1][w];
                    dp[i][w] = max(withItem, withoutItem);
                } else {
                    dp[i][w] = dp[i-1][w];
                }
        
        return dp[n][capacity];
    }
};

Problem Statement

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. You cannot break an item - either pick the complete item or don't pick it (0-1 property).

Category: Dynamic Programming | Difficulty: Medium

Detailed Explanation

Approach

The 0/1 Knapsack problem is solved using a 2D dynamic programming approach where we build our solution by considering each item and each possible weight capacity. For each item, we have two choices: include it or exclude it, and we take the maximum value possible from these choices.

Key Concepts

1. 2D DP Array: Unlike the unbounded knapsack, we need a 2D array because we can't reuse items. Each row i represents using items [0...i], and each column w represents the maximum value achievable with capacity w.

2. State Transition: The core decision for each state (i,w) is whether to include the current item or not. This creates our recurrence relation:

   dp[i][w] = max(
       value[i-1] + dp[i-1][w-weight[i-1]],  // include item
       dp[i-1][w]                            // exclude item
   )

3. Base Cases: First row and column are initialized to 0, representing no items or no capacity.

Algorithm Steps

1. Create a 2D DP array of size (n+1) × (capacity+1)

2. For each item i and capacity w:

   • If current item's weight fits (weights[i-1] ≤ w):
     • Try including the item: values[i-1] + dp[i-1][w-weights[i-1]]
     • Try excluding the item: dp[i-1][w]
     • Take maximum of these two choices
   • If item doesn't fit:
     • Must exclude the item: dp[i-1][w]

Visual Example

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

DP Table Evolution:
   0  10  20  30  40  50
0  0   0   0   0   0   0
1  0  60  60  60  60  60
2  0  60 100 160 160 160
3  0  60 100 160 180 220

Final answer: 220

Path to solution:
- Can fit item 3 (weight 30) + item 2 (weight 20): 120 + 100 = 220

Time and Space Complexity

• Time Complexity: O(n × capacity) - We fill each cell in our 2D table exactly once
• Space Complexity: O(n × capacity) - We need to store all intermediate results

Key Differences from Unbounded Knapsack

Unlike the Coin Change II problem (unbounded knapsack), we cannot reuse items. This is why we need to reference the previous row (i-1) when making our decisions. This requirement for previous state makes it impossible to optimize to a 1D array without losing necessary information.

Edge Cases

• Empty items list: Returns 0
• Capacity = 0: Returns 0
• Single item that fits perfectly: Returns its value
• No items that fit within capacity: Returns 0

Space Optimization Potential

While not shown in the code, it's possible to optimize the space complexity to O(capacity) by using two 1D arrays and alternating between them, since we only need the previous row's information. However, this makes the code more complex and harder to understand.

Common Applications

1. Resource allocation in resource-constrained environments
2. Portfolio optimization with indivisible assets
3. Cargo loading problems
4. Budget constrained procurement decisions