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 ; array to store final result dp [ i ] stores the profit with KnapSack capacity " i " ; 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 code
function KnapSack ( val , wt , n , W ) { let dp = new Array ( W + 1 ) ; for ( let i = 0 ; i < W + 1 ; i ++ ) { dp [ i ] = 0 ; } for ( let i = 0 ; i < n ; i ++ ) for ( let j = W ; j >= wt [ i ] ; j -- ) dp [ j ] = Math . max ( dp [ j ] , val [ i ] + dp [ j - wt [ i ] ] ) ; return dp [ W ] ; } let val = [ 7 , 8 , 4 ] ; let wt = [ 3 , 8 , 6 ] ; let W = 10 , n = 3 ; document . write ( KnapSack ( val , wt , n , W ) ) ;