Problem Statement

The 0/1 Knapsack Problem is a classic optimization problem where the goal is to determine the maximum value that can be obtained by selecting items with given weights and values, while not exceeding a maximum weight capacity of the knapsack. Each item can either be included in the knapsack (1) or excluded (0), hence the name “0/1”.

Approach Explanation

This problem can be solved using dynamic programming. The idea is to build a table that stores the maximum value that can be obtained with a given weight capacity for each item considered.

Dynamic Programming Structure:

1. Define a 2D DP table where dp[i][w] represents the maximum value that can be obtained with the first i items and a maximum weight w.
2. Initialize the first row and first column of the table with zeros, as no items or zero capacity yields a value of zero.
3. Iterate through the items. For each item, update the DP table by considering whether to include or exclude the item based on its weight and value.
4. The final answer will be found in dp[n][W], where n is the number of items and W is the maximum weight capacity of the knapsack.

Time Complexity:

O(n * W), where n is the number of items and W is the maximum weight capacity.

Space Complexity:

O(n * W) for the DP table.

Python Code

def knapsack(weights, values, W):
    """
    Function to solve the 0/1 Knapsack problem using dynamic programming.

    Args:
    weights (List[int]): List of weights for each item.
    values (List[int]): List of values for each item.
    W (int): Maximum weight capacity of the knapsack.

    Returns:
    int: Maximum value that can be obtained with the given weight capacity.
    """
    n = len(values)
    
    # Create a 2D DP table initialized to 0
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    # Fill the DP table
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][W]


# Example usage
weights = [1, 2, 3]
values = [60, 100, 120]
W = 5
max_value = knapsack(weights, values, W)

print("Maximum value in Knapsack =", max_value)
    

Explanation of the Program

Let’s break down the structure of the program:

1. Input:

The input consists of:

• A list of weights for each item.
• A list of values for each item.
• The maximum weight capacity of the knapsack.

    weights = [1, 2, 3]
    values = [60, 100, 120]
    W = 5

2. DP Table Initialization:

A DP table is created with dimensions (n + 1) x (W + 1), initialized to zeros. This table is used to store the maximum values obtainable for each combination of items and weight capacities.

3. Iteration Over Items and Weights:

The program iterates over each item and for each weight capacity, it checks whether the current item can be included in the knapsack. If it can, the program calculates the maximum value by comparing the value obtained by including the item versus excluding it.

4. Final Result:

The maximum value obtainable with the given weight capacity can be found in the bottom-right cell of the DP table: dp[n][W].

Example Execution:

For the provided input values and weights, the output will display the maximum value that can be obtained:

Maximum value in Knapsack = 220

This indicates that the maximum value obtainable from the given items without exceeding the weight capacity of 5 is 220.