Unbounded Knapsack ( Repetition of items allowed ) | Returns the maximum value with knapsack of W capacity ; dp [ i ] is going to store maximum value with knapsack capacity i . ; Fill dp [ ] using above recursive formula ; Driver Code
< ? php function unboundedKnapsack ( $ W , $ n , $ val , $ wt ) { for ( $ i = 0 ; $ i <= $ W ; $ i ++ ) $ dp [ $ i ] = 0 ; $ ans = 0 ; for ( $ i = 0 ; $ i <= $ W ; $ i ++ ) for ( $ j = 0 ; $ j < $ n ; $ j ++ ) if ( $ wt [ $ j ] <= $ i ) $ dp [ $ i ] = max ( $ dp [ $ i ] , $ dp [ $ i - $ wt [ $ j ] ] + $ val [ $ j ] ) ; return $ dp [ $ W ] ; } $ W = 100 ; $ val = array ( 10 , 30 , 20 ) ; $ wt = array ( 5 , 10 , 15 ) ; $ n = count ( $ val ) ; sizeof ( $ val ) / sizeof ( $ val [ 0 ] ) ; echo unboundedKnapsack ( $ W , $ n , $ val , $ wt ) ; ? >