Printing Items in 0 / 1 Knapsack | A utility function that returns maximum of two integers ; Prints the items which are put 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
function max ( a , b ) { return ( a > b ) ? a : b ; } function printknapSack ( W , wt , val , n ) { let i , w ; let K = new Array ( n + 1 ) ; for ( i = 0 ; i < K . length ; i ++ ) { K [ i ] = new Array ( W + 1 ) ; for ( let j = 0 ; j < W + 1 ; j ++ ) { K [ i ] [ j ] = 0 ; } } 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 ] = Math . max ( val [ i - 1 ] + K [ i - 1 ] [ w - wt [ i - 1 ] ] , K [ i - 1 ] [ w ] ) ; else K [ i ] [ w ] = K [ i - 1 ] [ w ] ; } } let res = K [ n ] [ W ] ; document . write ( res + " " ) ; w = W ; for ( i = n ; i > 0 && res > 0 ; i -- ) { if ( res == K [ i - 1 ] [ w ] ) continue ; else { document . write ( wt [ i - 1 ] + " " ) ; res = res - val [ i - 1 ] ; w = w - wt [ i - 1 ] ; } } } let val = [ 60 , 100 , 120 ] ; let wt = [ 10 , 20 , 30 ] ; let W = 50 ; let n = val . length ; printknapSack ( W , wt , val , n ) ;