0/1 knapsack algorithm in Python
Hello Coders, this tutorial deals with a Python program to implement the 0/1 knapsack algorithm.
0/1 knapsack in Python
Given the weights and values of n items, we need to transfer these items into a knapsack of wight/capacity W to get the maximum total value.
Now coming to coding, we are defining a function called knapsack. This knapsack() is a recursive function which takes arguments C(max_capacity), weights(list of weights), values(list of corresponding values), n(no. of items).
After that in this function, there are three conditional statements.
1. for checking whether n or C value is equal to 0.
2. for checking if that item weight is greater than the capacity of the bag if yes, then we are ignoring this item.
3. if that element is not greater than capacity then we are aging returning the maximum value if we take or not take that item.
So based on this recursion this function works.
Let us see the code of it.
def knapsack(C, weights, values, n): if(n==0 or C==0): return 0 if(weights[n-1]>C): return knapsack(C, weights, values, n-1) else: return max(values[n-1]+knapsack(C-weights[n-1], weights, values, n-1), knapsack(C,weights, values, n-1)) print('Enter the values:') values=list(map(int,input().split(' '))) print('Enter the weights:') weights=list(map(int,input().split(' '))) C=int(input('Enter the maximum capacity:')) n=len(weights) print(knapsack(C, weights, values, n))
For any queries please comment below.
Also read: Floyd Warshall Algorithm in Python