0 | Returns the maximum value that can be put in a knapsack of capacity W ; Base Case ; If weight of the nth item is more than Knapsack capacity W , then this item cannot be included in the optimal solution ; Return the maximum of two cases : ( 1 ) nth item included ( 2 ) not included ; Driver Code
< ? php function knapSack ( $ W , $ wt , $ val , $ n ) { if ( $ n == 0 $ W == 0 ) return 0 ; if ( $ wt [ $ n - 1 ] > $ W ) return knapSack ( $ W , $ wt , $ val , $ n - 1 ) ; else return max ( $ val [ $ n - 1 ] + knapSack ( $ W - $ wt [ $ n - 1 ] , $ wt , $ val , $ n - 1 ) , knapSack ( $ W , $ wt , $ val , $ n - 1 ) ) ; } $ val = array ( 60 , 100 , 120 ) ; $ wt = array ( 10 , 20 , 30 ) ; $ W = 50 ; $ n = count ( $ val ) ; echo knapSack ( $ W , $ wt , $ val , $ n ) ; ? >