
#  0-1 Knapsack Problem 
  
# Returns the maximum value that  
# can be put in a knapsack of  
# capacity W 
def knapSack(W, wt, val, n): 
  
    # Base Case 
    if n == 0 or W == 0 : 
        return 0

    if (wt[n-1] > W): 
        return knapSack(W, wt, val, n-1) 
  

    else: 
        return max( 
            val[n-1] + knapSack( 
                W-wt[n-1], wt, val, n-1),  
                knapSack(W, wt, val, n-1)) 
  
