A Space Optimized DP solution for 0 | val [ ] is for storing maximum profit for each weight wt [ ] is for storing weights n number of item W maximum capacity of bag dp [ W + 1 ] to store final result ; initially profit with 0 to W KnapSack capacity is 0 ; iterate through all items ; traverse dp array from right to left ; above line finds out maximum of dp [ j ] ( excluding ith element value ) and val [ i ] + dp [ j - wt [ i ] ] ( including ith element value and the profit with " KnapSack ▁ capacity ▁ - ▁ ith ▁ element ▁ weight " ) * ; Driver program to test the cases
def KnapSack ( val , wt , n , W ) : NEW_LINE INDENT dp = [ 0 ] * ( W + 1 ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( W , wt [ i ] , - 1 ) : NEW_LINE INDENT dp [ j ] = max ( dp [ j ] , val [ i ] + dp [ j - wt [ i ] ] ) ; NEW_LINE DEDENT DEDENT return dp [ W ] ; NEW_LINE DEDENT val = [ 7 , 8 , 4 ] ; NEW_LINE wt = [ 3 , 8 , 6 ] ; NEW_LINE W = 10 ; n = 3 ; NEW_LINE print ( KnapSack ( val , wt , n , W ) ) ; NEW_LINE