Python - Knapsack Problem

Python – Knapsack Problem

The Knapsack Problem is a classic optimization problem in computer science and dynamic programming. In this problem, you are given a set of items, each with a weight and a value, and a knapsack with a limited capacity. The goal is to determine the maximum total value of items that can be included in the knapsack without exceeding its capacity.

Problem Statement

Given n items where each item has a weight wt[i] and a value val[i], and a knapsack with capacity W, find the maximum value that can be achieved by selecting a subset of items such that the total weight does not exceed W. This is known as the 0/1 Knapsack Problem because each item can be chosen either once or not at all.

Sample Input and Output

Example 1:

</>

Copy

# Sample Input:
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

# Expected Output:
220

Explanation: In this example, there are three items. The values array [60, 100, 120] represents the profit of each item, while the weights array [10, 20, 30] represents their respective weights. The knapsack can hold a maximum weight of 50. Using dynamic programming, the algorithm evaluates each item and capacity combination. It determines that the optimal solution is achieved by including the items with values 100 and 120 (with a total weight of 20 + 30 = 50), which gives the maximum value of 220.

Example 2:

</>

Copy

# Sample Input:
values = [10, 40, 30, 50]
weights = [5, 4, 6, 3]
capacity = 10

# Expected Output:
90

Explanation: Here, we have four items with values [10, 40, 30, 50] and corresponding weights [5, 4, 6, 3]. The knapsack capacity is 10. The dynamic programming approach considers all possible combinations of these items under the weight constraint. In this case, the best combination is to choose the items with values 40 and 50 (having weights 4 and 3 respectively) since their combined weight is 7 (which is within the capacity) and their combined value is 90, which is the maximum value attainable given the constraints.

Solution Approach

We will use Dynamic Programming to solve the Knapsack Problem efficiently. The main idea is to build a 2D table dp where:

Initialization: Create a table dp with dimensions (n+1) x (W+1), where dp[i][w] represents the maximum value achievable with the first i items and a knapsack capacity of w. Initialize the first row and first column with 0, since no items or zero capacity yields 0 value.
Recurrence Relation: For each item i (1 ≤ i ≤ n) and each capacity w (1 ≤ w ≤ W):
- If the item’s weight is less than or equal to the current capacity (wt[i-1] ≤ w), then:
  dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w])
- Otherwise, the item cannot be included:
  dp[i][w] = dp[i-1][w]
Result: The value at dp[n][W] will be the maximum value that can be achieved with the given items and knapsack capacity.

Python Program

Below is a complete Python program that implements the dynamic programming solution for the Knapsack Problem:

</>

Copy

def knapsack(W, weights, values, n):
    # Create a DP table with dimensions (n+1) x (W+1)
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
    
    # Build the DP table in bottom up manner
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i - 1] <= w:
                # Maximum value obtained by either including the current item or not including it
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][W]

# Example 1:
values1 = [60, 100, 120]
weights1 = [10, 20, 30]
capacity1 = 50
n1 = len(values1)
print("Maximum value for Example 1:", knapsack(capacity1, weights1, values1, n1))

# Example 2:
values2 = [10, 40, 30, 50]
weights2 = [5, 4, 6, 3]
capacity2 = 10
n2 = len(values2)
print("Maximum value for Example 2:", knapsack(capacity2, weights2, values2, n2))

Solution using Combinations

</>

Copy

from itertools import combinations

def knapsack(W, weights, values, n):
    # indices for weights and values
    indices = list(range(0, len(weights)))
    # maximum sum of values
    max_value = 0
    
    # for different lengths of combinations of weights
    for i in range(1, len(weights) + 1):
        # for each subset with the combinations of indices of length i
        for subset in list(combinations(indices, i)):
            # find the sum of weights for the combination of indices
            sum_of_weights = sum([weights[weight_index] for weight_index in subset])
            if sum_of_weights <= W:
                # find sum of values for the indices in combination
                sum_of_values = sum([values[weight_index] for weight_index in subset])
                max_value = max(sum_of_values, max_value)

    return max_value        
    
# Example 1:
values1 = [60, 100, 120]
weights1 = [10, 20, 30]
capacity1 = 50
n1 = len(values1)
print("Maximum value for Example 1:", knapsack(capacity1, weights1, values1, n1))

# Example 2:
values2 = [10, 40, 30, 50]
weights2 = [5, 4, 6, 3]
capacity2 = 10
n2 = len(values2)
print("Maximum value for Example 2:", knapsack(capacity2, weights2, values2, n2))

Conclusion

In this tutorial, we explored the Knapsack Problem using dynamic programming. We defined the problem, walked through sample inputs and outputs, and explained the step-by-step solution approach. Finally, we implemented a Python program that demonstrates how to solve the problem using a 2D DP table. This approach efficiently computes the maximum value that can be carried in the knapsack while staying within the given capacity.

TutorialKart

Python – Knapsack Problem