0/1 Knapsack Problem

0/1 Knapsack Problem

The 0/1 Knapsack Problem is a classic optimization problem where, given a set of items (each with a weight and a value) and a knapsack with a maximum weight capacity, the goal is to determine the subset of items to include in the knapsack to maximize the total value without exceeding the capacity. Each item can either be included (1) or excluded (0), with no partial selection allowed. The problem is solved efficiently using dynamic programming with a time complexity of O(n * W), where n is the number of items and W is the knapsack capacity.

Example

• Input: values = [60, 100, 120], weights = [10, 20, 30], capacity = 50
• Output: 220
• Explanation: Including items with values 100 and 120 (weights 20 and 30) gives the maximum value of 220 within the capacity of 50.

Program (Python - 0/1 Knapsack using Dynamic Programming)

The following Python code implements the 0/1 Knapsack algorithm using dynamic programming with O(n * W) time complexity and O(n * W) space complexity.

def knapsack(values, weights, capacity):
    n = len(values)
    # Create a 2D DP table
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    # Fill the DP table
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                # Include or exclude the current item
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                # Exclude the current item
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][capacity]

# Example usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(knapsack(values, weights, capacity))  # Output: 220

220