0 | Returns the maximum value that can be put in a knapsack of capacity W ; Build table K [ ] [ ] in bottom up manner ; Driver Code
< ? php function knapSack ( $ W , $ wt , $ val , $ n ) { $ K = array ( array ( ) ) ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) { for ( $ w = 0 ; $ w <= $ W ; $ w ++ ) { if ( $ i == 0 $ w == 0 ) $ K [ $ i ] [ $ w ] = 0 ; else if ( $ wt [ $ i - 1 ] <= $ w ) $ K [ $ i ] [ $ w ] = max ( $ val [ $ i - 1 ] + $ K [ $ i - 1 ] [ $ w - $ wt [ $ i - 1 ] ] , $ K [ $ i - 1 ] [ $ w ] ) ; else $ K [ $ i ] [ $ w ] = $ K [ $ i - 1 ] [ $ w ] ; } } return $ K [ $ n ] [ $ W ] ; } $ val = array ( 60 , 100 , 120 ) ; $ wt = array ( 10 , 20 , 30 ) ; $ W = 50 ; $ n = count ( $ val ) ; echo knapSack ( $ W , $ wt , $ val , $ n ) ; ? >