#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 , val , n): 

	# Base Case 
	if n == 0 or W == 0 : 
		return 0

	# If weight of the nth item is more than Knapsack of capacity 
	# W, then this item cannot be included in the optimal solution 
	if (wt[n-1] > W): 
		return knapSack(W , wt , val , n-1) 

	# return the maximum of two cases: 
	# (1) nth item included 
	# (2) not included 
	else: 
		return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), 
				knapSack(W , wt , val , n-1)) 

# end of function knapSack 

# To test above function 
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val)
print('slowSack:')
print (knapSack(W , wt , val , n))

# This code is contributed by <NAME>


# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W 
def dynamicSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1): 
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
  
# Driver program to test above function 
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val)
print('dynamicSack:')
print(dynamicSack(W, wt, val, n)) 
  
# This code is contributed by <NAME> 


#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 , val , n): 

	# Base Case 
	if n == 0 or W == 0 : 
		return 0

	# If weight of the nth item is more than Knapsack of capacity 
	# W, then this item cannot be included in the optimal solution 
	if (wt[n-1] > W): 
		return knapSack(W , wt , val , n-1) 

	# return the maximum of two cases: 
	# (1) nth item included 
	# (2) not included 
	else: 
		return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), 
				knapSack(W , wt , val , n-1)) 

# end of function knapSack 

# To test above function 
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val)
print('slowSack:')
print (knapSack(W , wt , val , n))

# This code is contributed by <NAME>


# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W 
def dynamicSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1): 
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
  
# Driver program to test above function 
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val)
print('dynamicSack:')
print(dynamicSack(W, wt, val, n)) 
  
# This code is contributed by <NAME> 


#A naive recursive implementation of 0-1 Knapsack Problem # Returns the maximum value that can be put in a knapsack of # capacity W # Base Case # If weight of the nth item is more than Knapsack of capacity # W, then this item cannot be included in the optimal solution # return the maximum of two cases: # (1) nth item included # (2) not included # end of function knapSack # To test above function # This code is contributed by <NAME> # A Dynamic Programming based Python Program for 0-1 Knapsack problem # Returns the maximum value that can be put in a knapsack of capacity W # Build table K[][] in bottom up manner # Driver program to test above function # This code is contributed by <NAME>