#Consider the sack of capacity 5 kg.
# We have 4 items
# #1 ➠ 2 kg. worth 12$ ➠ (2,12)
# #2 ➠ 1 kg. worth 10$ ➠ (1,10)
# #3 ➠ 3 kg. worth 20$ ➠ (3,20)
# #4 ➠ 2 kg. worth 15$ ➠ (2,15)

# This code is contributed by Nikhil Kumar Singh 
def naive_knapSack(W, wt, val, n): 
   
    if n == 0 or W == 0 : 
        return 0
  
    if (wt[n-1] > W): 
        return naive_knapSack(W, wt, val, n-1) 
  
    else: 
        return max(val[n-1] + naive_knapSack(W-wt[n-1], wt, val, n-1), 
                   naive_knapSack(W, wt, val, n-1)) 


# This code is contributed by Bhavya Jain 
def dynamic_knapSack(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] 

val = [12, 10, 20, 15] 
wt = [2, 1, 3, 2] 
W = 5
n = len(val) 

print("Naive knapsack: ")
print(naive_knapSack(W, wt, val, n)) 

print("Dynamic programming knapsack: ")
print(dynamic_knapSack(W, wt, val, n))