Solving the 0-1 Knapsack Problem in Python using Recursion

Feature Img Knapsack Problem

Hi guys! In this tutorial, I am trying to explain the knapsack problem. You will encounter the problem somewhere or another during the interviews.

We will be using the Recursion approach in order to solve the problem. If you are unaware of how recursion works take a look at the tutorial below.

Read more about Recursion: Recursion in Python

Introduction to Knapsack Problem

There’s a thief with a knapsack that can hold a total weight of capacity. He has n items to steal from the place having different weights and prices.

01 Knapsack Problem
01 Knapsack Problem

Our aim is to create a function called knapsack that will find out a subset of these items resulting in the maximum profit for the thief considering the total weight of all the items does not exceed the given capacity of the knapsack.

Also read: Solving the Friends-Travel Problem in Python [Google Interview Question]

The same is illustrated in the image below.

01 Knapsack Problem 1
01 Knapsack Problem 1

Solution to the Knapsack Problem in Python using Recursion

We will be considering that for each item the thief has two options: Either to include the item or to exclude the item and don’t pick it up.

If the thief includes an item, we will be searching for maximum profit for the remaining n-1 items and will also decrease the capacity by the weight of the item included.

The total profit, in this case, would be: the price of item + Profit in n-1 items for (capacity – the weight of the item) remaining

And if a person excludes the item, we will just find the profit for the remaining n-1 items from the store. The profit, in this case, will be: Profit in n-1 items for capacity remaining

The final answer would be the maximum profit from both cases.

Code Implementation

def knapsack(n,capacity,weights,prices):
    if(n==0 or capacity==0):
        return 0

    if (weights[n-1]>capacity):
        return knapsack(n-1,capacity,weights,prices)
        return max(prices[n-1] + knapsack(n-1,capacity-weights[n-1],weights,prices),

weights = [1,2,3,4]
prices = [50,200,150,100]
n = 4
capacity = 7


The output received after the execution of the current code came out to be 400 which is the correct output.

Thank you for taking the time for reading the tutorial! I hope the Knapsack problem is clear to you now.

Happy learning! 😇