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 mean 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
< ? php function KnapSack ( & $ val , & $ wt , $ n , $ W ) { $ mat = array_fill ( 0 , 2 , array_fill ( 0 , $ W + 1 , NULL ) ) ; $ i = 0 ; while ( $ i < $ n ) { $ j = 0 ; if ( $ i % 2 != 0 ) { { while ( ++ $ j <= $ W ) if ( $ wt [ $ i ] <= $ j ) $ mat [ 1 ] [ $ j ] = 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 ] = max ( $ val [ $ i ] + $ mat [ 1 ] [ $ j - $ wt [ $ i ] ] , $ mat [ 1 ] [ $ j ] ) ; else $ mat [ 0 ] [ $ j ] = $ mat [ 1 ] [ $ j ] ; } } $ i ++ ; } if ( $ n % 2 != 0 ) return $ mat [ 0 ] [ $ W ] ; else return $ mat [ 1 ] [ $ W ] ; } $ val = array ( 7 , 8 , 4 ) ; $ wt = array ( 3 , 8 , 6 ) ; $ W = 10 ; $ n = 3 ; echo KnapSack ( $ val , $ wt , $ n , $ W ) . " STRNEWLINE " ; ? >