0-1 Knapsack Problem - Recursive
# recursive solution
# time complexity: O(2^n) since there are 2 paths for each item
# w - current capacity of the sack
# weights - an array containing all the weights of n items
# values - an array containing all the values of n items
# n - a pointer to the nth item we are considering
def knap_sack_recursive(w, weights, values, n):
# base case
# if there are 0 items to consider, or if the sack capacity has reached 0, we return 0
if(n == 0 or w == 0):
return 0
# if weight of nth item is more than knapsack capacity w,
# then, this item cannot be included in optimal solution
# we skip it and recurse with (n-1) items
elif(weights[n-1] > w):
return knap_sack_recursive(w, weights, values, n-1)
# we consider 2 cases: when we include and when we exclude the current (nth) item
# we return whichever gives us the better value
else:
return max(values[n-1] + knap_sack_recursive(w - weights[n-1], weights, values, n-1),
knap_sack_recursive(w, weights, values, n-1))