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))
Enter the maximum limit for the bag: 97 The maximum value of items we can get with the given limit: 2565
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))
Enter the maximum limit for the bag: 69 The maximum value of items we can get with the given limit: 2115
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.
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.