Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# input
# values stored in array v
# wighets stored in array wt
#length of array n
# knapsack capcity stored in w
#A naive recursive implementation of 0-1 Knapsack Problem
# Returns the maximum value that can be put in a knapsack of
# capacity W
def knapSack(w, wt, v, n):
# base case
if n == 0 or w == 0:
return 0
# if weight of the nth item is more than knapsack of capcity
# w then this item cannot be included in the optimal solution
if(wt[n-1] > w):
return knapSack(w, wt, v, n-1)
# return the maximum of two cases
# (1) nth item included
# (2) not included
else:
return max(v[n-1] + knapSack(w-wt[n-1], wt , v, n-1), knapSack(w, wt, v, n-1))
# end of function knapSack
v = [100, 40, 70]
wt = [4, 2, 3]
w = 5
n = len(v)
print knapSack(w, wt, v, n)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment