Solving 0/1 Knapsack Using Dynamic programming in Python

By /
0:1 Knapsack

In this article, we’ll solve the 0/1 Knapsack problem using dynamic programming.

Dynamic Programming is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

0/1 Knapsack is perhaps the most popular problem under Dynamic Programming. It is also a great problem to learn in order to get a hang of Dynamic Programming.

In this tutorial, we will be learning about what exactly is 0/1 Knapsack and how can we solve it in Python using Dynamic Programming.

Let’s get started.

Problem Statement for 0/1 Knapsack

The problem statement of Dynamic programming is as follows :

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

To begin with, we have a weight array that has the weight of all the items. We also have a value array that has the value of all the items and we have a total weight capacity of the knapsack.

Given this information, we need to find the maximum value we can get while staying in the weight limit.

The problem is called 0/1 knapsack because we can either include an item as a whole or exclude it. That is to say, we can’t take a fraction of an item.

Let’s take an example to understand.

Take the following input values.

val = [50,100,150,200]
wt = [8,16,32,40]
W = 64

Here we get the maximum profit when we include items 1,2 and 4 giving us a total of 200 + 50 + 100 = 350.

Therefore the total profit comes out as :

350

How to solve 0/1 Knapsack using Dynamic Programming?

To solve 0/1 knapsack using Dynamic Programming we construct a table with the following dimensions.

[n + 1][W + 1]

The rows of the table correspond to items from 0 to n.

The columns of the table correspond to weight limit from 0 to W.

The index of the very last cell of the table would be :

[n][W]

Value of the cell with index [i][j] represents the maximum profit possible when considering items from 0 to i and the total weight limit as j.

After filling the table our answer would be in the very last cell of the table.

How to fill the table?

Let’s start by setting the 0th row and column to 0. We do this because the 0th row means that we have no objects and the 0th column means that the maximum weight possible is 0.

Now for each cell [i][j], we have two options :

  1. Either we include object [i] in our final selection.
  2. Or we don’t include object [i] in our final selection.

How do we decide whether we include object [i] in our selection?

There are two conditions that should be satisfied to include object [i] :

  1. The total weight after including object [i] should not exceed the weight limit.
  2. The profit after including object [i] should be greater as compared to when the object is not included.

Let’s convert our understanding of 0/1 knapsack into python code.

Python Code to solve 0/1 Knapsack

Let’s create a table using the following list comprehension method:

table = [[0 for x in range(W + 1)] for x in range(n + 1)]

We will be using nested for loops to traverse through the table and fill entires in each cell.

We are going to fill the table in a bottom up manner.

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

Let’s breakdown the code line by line. 

  if i == 0 or j == 0: 
     table[i][j] = 0

This part of the code is responsible for setting the 0th row and column to 0.

 elif wt[i-1] <= j:

This line of code checks that the weight of the i(th) object is less that the total weight permissible for that cell (j).

 table[i][j] = max(val[i-1]  
+ table[i-1][j-wt[i-1]],  table[i-1][j])

This line of code is responsible for selecting the maximum out of the two options available to us. We can either include the object or exclude it.

Here the term table[i – 1][j] means that ith item is not included. The term val[i – 1] + table[i – 1][j – wt[i – 1]] represents that the ith item is included.

else:
  table[i][j] = table[i-1][j]

This part of the loop is accessed when the weight of ith object is greater than the permissible limit (j).

When we are done filling the table we can return the last cell of the table as the answer.

return table[n][W]

Complete code for the Knapsack solving function

The complete code for the function that solves the knapsack is given below :

def knapSack(W, wt, val): 
    n=len(val)
    table = [[0 for x in range(W + 1)] for x in range(n + 1)] 

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

Let’s try running the function for the example we took above.

val = [50,100,150,200]
wt = [8,16,32,40]
W = 64

print(knapSack(W, wt, val))

Complete Code

Here’s the complete code for you to run on your system.

def knapSack(W, wt, val): 
    n=len(val)
    table = [[0 for x in range(W + 1)] for x in range(n + 1)] 

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

val = [50,100,150,200]
wt = [8,16,32,40]
W = 64

print(knapSack(W, wt, val))

Upon running the code, we get the following output :

350

Conclusion

This tutorial was about solving 0/1 Knapsack using Dynamic programming in Python. We hope you had fun learning with us!