Python Knapsack problem

Python Knapsack problem

Before we dig down about Knapsack problems in Python, first let's have a look at what is actually a knapsack problem.

What is a knapsack problem?

A problem from the optimization combinational related issues is known as a knapsack problem. This problem often arises in our daily life in resources allocations where the decisions have to be made from the set of items that are non-divisible tasks or projects which are placed under a fixed budget constraints or time constraint.

Example of knapsack problem

Suppose we have given a set of items; each have a given value (in terms of money on anything) and a given weight such as the total combine weight of items is more than the actual limit. So, here we have to maximize the value within the limit. It means we have to choose the items that have more value and less weight and that's how we can get maximum value within the limit.

This is the classical example of a one-dimensional Knapsack problem.

Note:The word Knapsack itself means a 'bag'.

Knapsack Problem in Python

As of now, we have a basic understanding about the knapsack problems and how a one-dimensional Knapsack problem looks like. Here, in this tutorial, we will discuss about that how we can solve the knapsack problem using Python. We will take 2 example knapsack problems and design a Python program for each to solve them with the dynamic programming. And, after that we will see the explanation of the program to understand the logic and working of it.

• Important:The knapsack problem (particularly of one-dimension) is referred to as 0/1 knapsack problem in Python and it is the most popular type problem in a dynamically typed programming language.

Now, let's discuss about a 0/1 knapsack problem and approaches we are using to design its solution program in Python. Basically, we use any of the following two approaches to design a solution Python program for any 0/1 knapsack problem:

1. Designing solution program using Brute-force approach

2. Designing solution program using dynamic approach

Let's see their implementation of these approaches.

Given 0/1 knapsack problem

We have a given number of items and these items have their respective weight and value. We have to place these items inside a bag that have a weighing capacity (Let's say W). We have to get the maximum value in the bag from the given items and we have to answer the maximum number of values that we can get in the bag within the limit of it.

Solution 1: Using Brute-force approach in solution program:

 # Define a default knapsack 01 function
 def knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI):
    # Give the initial if conditions
    if NumberOI == 0 or MLimit == 0 :
       return 0
    # Defining nested if condition for higher weight
    if (WeightofItem [NumberOI-1] > MLimit):
       return knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI-1)
    # Using else condition for number of items
    else:
       return max (ValueofItem [NumberOI-1] + knapsack01 (MLimit-WeightofItem [NumberOI-1], WeightofItem, ValueofItem, NumberOI-1),
          knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI-1))
 # Defining variables used in the function
 ValueofItem = [5, 10, 20, 50, 100, 200, 500, 2000]
 WeightofItem = [1, 4, 8, 16, 24, 32, 36, 40]
 NumberOI = len (ValueofItem)
 # Taking maximum limit as user input
 MLimit = int (input ("Enter the maximum limit for the bag: "))
 # Printing result of problem in the output
 print ("The maximum value of items we can get with the given limit: ")
 print (knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI)) 

Output:

 Enter the maximum limit for the bag: 97
 The maximum value of items we can get with the given limit:
 2565 

Explanation:

 In this program, we have implemented the brute-force approach for the solution of given problem. We have defined a knapsack function and give variables of the problems i.e., Maximum limit of bag, Weight of each item, Value of each item and Number of items, as the arguments in this function.

Then, we used nested if else condition in the function with the given variables to apply the brute-force approach in the program.

We get maximum value and all the findings in this nested if else condition. After that, we have defined the values of the given variables in function i.e., Values of items, Weight of items and number of items respectively in list format.

After that, we defined the maximum limit of the bag variable to user input. After that, we called out the function to print the result as maximum value can be stored in bag. When the program will get the maximum limit of bag as user input, the result for maximum value in the bag with respect to maximum limit, will be printed in the output.

Solution 2: Using dynamic approach in solution program:

 # Define a default knapsack 01 function
 def knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI):
    M = [ [0 for a in range (MLimit + 1)] for a in range (NumberOI + 1)]
    # Define a for loop for limit
    for b in range (NumberOI + 1):
       # Nested for loop for higher limit
       for c in range (MLimit + 1):
          # Defining if condition for maximum weight
          if b == 0 or c == 0:
             M[b][c] = 0
          # Elseif condition for maximum value in bag
          elif WeightofItem[b-1] <= c:
             M[b][c] = max (ValueofItem[b-1] + M[b-1][c-WeightofItem[b-1]], M[b-1][c])
          else:
             M[b][c] = M[b-1][c]
    return M[NumberOI][MLimit] # returning maximum value from the function
 # Defining variables used in the function
 ValueofItem = [5, 10, 20, 50, 100, 200, 500, 2000]
 WeightofItem = [1, 4, 8, 16, 24, 32, 36, 40]
 NumberOI = len (ValueofItem)
 # Taking maximum limit as user input
 MLimit = int (input ("Enter the maximum limit for the bag: "))
 # Printing result of problem in the output
 print ("The maximum value of items we can get with the given limit: ")
 print (knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI)) 

Output:

 Enter the maximum limit for the bag: 69
 The maximum value of items we can get with the given limit:
 2115 

Explanation –

In this program, after defining the knapsack function we used the dynamic approach in the function.

We used nested for loop with the arguments of the function. In the nested for loop, we have defined a nested if else condition.

We used variables in the elseif and if condition to get the maximum value result. Then, we have defined variable values in list format and get the user input of maximum limit. We get the result of maximum value of bag using dynamic approach after giving maximum limit of bag as user input.

Conclusion:

In this tutorial, we learned about knapsack problem. We learned about knapsack 0/1 problem in Python. We also learned about the both approaches i.e., brute-force approach & dynamic approach, that we use in our Python program to solve the knapsack 0/1 problem.