Solution using 0 1 knapsack
k = np . zeros ( ( N + 1 , A + 1 ) ) NEW_LINE for i in range ( N + 1 ) : NEW_LINE INDENT for w in range ( A + 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 ] [ A ] ; NEW_LINE