Oct 16, 2019
diff --git a/Dynamic Programming/knapsack.py b/Dynamic Programming/knapsack.py
 # 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))


 # To test above function
 val = [60, 100, 120]
 wt = [10, 20, 30]
 W = 50
 n = len(val)
 print(knapSack(W , wt , val , n))
 # output 220
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,28 @@
		# 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))


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