Cacher is the code snippet organizer for pro developers

# 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))