Algorithms practice on Knapsack problem by Dynamic Programming

Level: Blue

Knapsack (backpack) Problem

Problem Statement:

The goal is to determine the maximum value you can achieve by selecting a subset of items such that their total weight does not exceed W.

Problem Example:

weights = [6, 3, 12] A list of weights representing the weight of each item.
values = [20, 5, 10] A list of values representing the value of each item.
capacity = 21 A maximum capacity W of the knapsack.

Solution: Dynamic Programming Approach

def knapsack(weights, values, W):
    n = len(weights)

    # Create a DP table where dp[i][w] represents the maximum value for the first i items with weight limit w
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    # Fill the DP table
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                p = weights[i - 1]
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - p] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            print (f"[{i}][{w}]=",dp[i][w], end=" ")
        print ("\n")

    # The result is the bottom-right cell of the DP table
    return dp[n][W]

# Example Usage
weights = [6, 3, 12]
values = [20, 5, 10]
capacity = 21

print("Maximum value:", knapsack(weights, values, capacity))

Output

knapsack.py 
[1][0]= 0 [1][1]= 0 [1][2]= 0 [1][3]= 0 [1][4]= 0 [1][5]= 0 [1][6]= 20 [1][7]= 20 [1][8]= 20 [1][9]= 20 [1][10]= 20 [1][11]= 20 [1][12]= 20 [1][13]= 20 [1][14]= 20 [1][15]= 20 [1][16]= 20 [1][17]= 20 [1][18]= 20 [1][19]= 20 [1][20]= 20 [1][21]= 20 

[2][0]= 0 [2][1]= 0 [2][2]= 0 [2][3]= 5 [2][4]= 5 [2][5]= 5 [2][6]= 20 [2][7]= 20 [2][8]= 20 [2][9]= 25 [2][10]= 25 [2][11]= 25 [2][12]= 25 [2][13]= 25 [2][14]= 25 [2][15]= 25 [2][16]= 25 [2][17]= 25 [2][18]= 25 [2][19]= 25 [2][20]= 25 [2][21]= 25 

[3][0]= 0 [3][1]= 0 [3][2]= 0 [3][3]= 5 [3][4]= 5 [3][5]= 5 [3][6]= 20 [3][7]= 20 [3][8]= 20 [3][9]= 25 [3][10]= 25 [3][11]= 25 [3][12]= 25 [3][13]= 25 [3][14]= 25 [3][15]= 25 [3][16]= 25 [3][17]= 25 [3][18]= 30 [3][19]= 30 [3][20]= 30 [3][21]= 35 

Maximum value: 35

Process finished with exit code 0

Explanation of the Code:

Dynamic Programming Table (DP):

Get Lake22’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

dp[i][w] holds the maximum value that can be obtained using the first i items, with a weight limit w. In this example, dp[2][5] holds value 5 for 2 items with weight capacity as 5.

Recurrence Relation:

• If the current item’s weight is less than or equal to the current weight limit w, we have two choices:
• Include the item: The previous known best weight for the weight without the current weight isw - weights[i-1], then add the new weight + values[i-1]. if this new value is greater than last know best value, then include it. In this example,
• dp[3][17] = dp [2][5] + 10 = 15 (capacity 17 is capacity 5 + capacity 12), the value is 5 + 10 = 15), small than dp[2][17] (previous known best value for capacity as 17), so keep max valule of dp[2][17] as 25
• dp[2][18] = dp[3][6] + 10 = 25 + 10 = 30 (greater than dp [2][18] as 25, so take this 30).
• Otherwise: Just take the value from the previous row: dp[i-1][w]

Key Learnings:

Dynamic Programming (DP) for Optimization:

• setup a single array with w, keep the highest value for each capacity, then loop through each item. add it to the previous know best value with the new vaule.