#! python3

"""
# knapsack problem
# Given weights and values of n items, 
# put these items in a knapsack of capacity W 
# to get the maximum total value in the knapsack.
# The brute-force method has time complexity of 2^N
# But using dynamic programming and bottom-up approach
# it can be reduced to O(n*W)
"""

# --------------------------------------------------------------
def knapSack(W, wt, val): 
    """
    # W - max weight of knapSack
    # wt - list of weights
    # val - list of values
    # n - number
    """
    n = len(val) 
    # ---------------------------------
    # create 2-dim array with (n+1) rows and (W+1) columns
    # populate with zeros
    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] 
  
# --------------------------------------------------------------
# main part
# --------------------------------------------------------------
val = [60, 100, 120] 
wt  = [10, 20, 30] 
W   = 50  # total weight allowed in knapSack


print(knapSack(W, wt, val, n)) 
