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