0 | Returns the maximum value that can be put in a knapsack of capacity W ; Build table K [ ] [ ] in bottom up manner ; Driver code
def knapSack ( W , wt , val , n ) : NEW_LINE INDENT K = [ [ 0 for x in range ( W + 1 ) ] for x in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for w in range ( W + 1 ) : NEW_LINE INDENT if i == 0 or w == 0 : NEW_LINE INDENT K [ i ] [ w ] = 0 NEW_LINE DEDENT elif wt [ i - 1 ] <= w : NEW_LINE INDENT K [ i ] [ w ] = max ( val [ i - 1 ] + K [ i - 1 ] [ w - wt [ i - 1 ] ] , K [ i - 1 ] [ w ] ) NEW_LINE DEDENT else : NEW_LINE INDENT K [ i ] [ w ] = K [ i - 1 ] [ w ] NEW_LINE DEDENT DEDENT DEDENT return K [ n ] [ W ] NEW_LINE DEDENT val = [ 60 , 100 , 120 ] NEW_LINE wt = [ 10 , 20 , 30 ] NEW_LINE W = 50 NEW_LINE n = len ( val ) NEW_LINE print ( knapSack ( W , wt , val , n ) ) NEW_LINE