Printing Items in 0 / 1 Knapsack | Prints the items which are kept in a knapsack of capacity W ; Build table K [ ] [ ] in bottom up manner ; stores the result of Knapsack ; either the result comes from the top ( K [ i - 1 ] [ w ] ) or from ( val [ i - 1 ] + K [ i - 1 ] [ w - wt [ i - 1 ] ] ) as in Knapsack table . If it comes from the latter one / it means the item is included . ; This item is included . ; Since this weight is included its value is deducted ; Driver code
< ? php function printknapSack ( $ W , & $ wt , & $ val , $ n ) { $ K = array_fill ( 0 , $ n + 1 , array_fill ( 0 , $ W + 1 , NULL ) ) ; 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 ] ; } } $ res = $ K [ $ n ] [ $ W ] ; echo $ res . " STRNEWLINE " ; $ w = $ W ; for ( $ i = $ n ; $ i > 0 && $ res > 0 ; $ i -- ) { if ( $ res == $ K [ $ i - 1 ] [ $ w ] ) continue ; else { echo $ wt [ $ i - 1 ] . " " ; $ res = $ res - $ val [ $ i - 1 ] ; $ w = $ w - $ wt [ $ i - 1 ] ; } } } $ val = array ( 60 , 100 , 120 ) ; $ wt = array ( 10 , 20 , 30 ) ; $ W = 50 ; $ n = sizeof ( $ val ) ; printknapSack ( $ W , $ wt , $ val , $ n ) ; ? >