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 mat [ 2 ] [ W + 1 ] to store final result ; matrix to store final result ; iterate through all items ; one by one traverse each element ; traverse all weights j <= W ; if i is odd that mean till now we have odd number of elements so we store result in 1 th indexed row ; check for each value ; include element ; exclude element ; if i is even that means till now we have even number of elements so we store result in 0 th indexed row ; Return mat [ 0 ] [ W ] if n is odd , else mat [ 1 ] [ W ] ; Driver Code
function KnapSack ( val , wt , n , W ) { let mat = new Array ( 2 ) ; for ( let i = 0 ; i < 2 ; i ++ ) { mat [ i ] = new Array ( W + 1 ) ; } for ( let i = 0 ; i < 2 ; i ++ ) { for ( let j = 0 ; j < W + 1 ; j ++ ) { mat [ i ] [ j ] = 0 ; } } let i = 0 ; while ( i < n ) { let j = 0 ; if ( i % 2 != 0 ) { while ( ++ j <= W ) { if ( wt [ i ] <= j ) { mat [ 1 ] [ j ] = Math . max ( val [ i ] + mat [ 0 ] [ j - wt [ i ] ] , mat [ 0 ] [ j ] ) ; } else { mat [ 1 ] [ j ] = mat [ 0 ] [ j ] ; } } } else { while ( ++ j <= W ) { if ( wt [ i ] <= j ) { mat [ 0 ] [ j ] = Math . max ( val [ i ] + mat [ 1 ] [ j - wt [ i ] ] , mat [ 1 ] [ j ] ) ; } else { mat [ 0 ] [ j ] = mat [ 1 ] [ j ] ; } } } i ++ ; } return ( n % 2 != 0 ) ? mat [ 0 ] [ W ] : mat [ 1 ] [ W ] ; } let val = [ 7 , 8 , 4 ] ; let wt = [ 3 , 8 , 6 ] ; let W = 10 , n = 3 ; document . write ( KnapSack ( val , wt , n , W ) ) ;