0/1 Knapsack Problem Using Dynamic Programming Code

5 min read Jul 17, 2024

0/1 Knapsack Problem using Dynamic Programming Code

Introduction

The 0/1 Knapsack Problem is a classic problem in Computer Science and Operations Research that involves finding the optimal way to pack a set of items of different weights and values into a knapsack of limited capacity. The problem is known as the 0/1 Knapsack Problem because we can either include an item in the knapsack (1) or not include it (0).

In this article, we will discuss how to solve the 0/1 Knapsack Problem using Dynamic Programming.

Problem Statement

Given a set of items, each with a weight w_i and a value v_i, determine the subset of items to include in a knapsack of capacity W that maximizes the total value while not exceeding the knapsack capacity.

Dynamic Programming Solution

The Dynamic Programming solution to the 0/1 Knapsack Problem involves creating a 2D table dp of size (W+1) x (n+1), where n is the number of items. The table dp is used to store the maximum value that can be obtained with a knapsack of capacity i using the first j items.

The following is the Dynamic Programming code in Python:

def knapsack(W, wt, val, n):
    dp = [[0 for w in range(W + 1)] for i in range(n + 1)]

    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]],  dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]

# Example usage
val = [60, 100, 120]  # values of items
wt = [10, 20, 30]  # weights of items
W = 50  # knapsack capacity
n = len(val)

print("Maximum value:", knapsack(W, wt, val, n))

How it Works

The Dynamic Programming solution works by building up the solution to the problem in a bottom-up manner. The table dp is filled in row by row, starting from the first row.

For each cell dp[i][w], we consider two possibilities:

If the item i-1 is included in the knapsack, we add its value to the maximum value that can be obtained with the remaining capacity w-wt[i-1] using the first i-1 items.
If the item i-1 is not included in the knapsack, we use the maximum value that can be obtained with the same capacity w using the first i-1 items.

The maximum value that can be obtained with a knapsack of capacity W using all n items is stored in the cell dp[n][W].

Conclusion

In this article, we have discussed how to solve the 0/1 Knapsack Problem using Dynamic Programming. The Dynamic Programming solution has a time complexity of O(nW) and a space complexity of O(nW), making it an efficient solution for the problem.

0/1 Knapsack Problem Using Dynamic Programming Code