Printing Items in 0 / 1 Knapsack | 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 ; Driver code
def printknapSack ( W , wt , val , n ) : NEW_LINE INDENT K = [ [ 0 for w in range ( W + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for w in range ( W + 1 ) : NEW_LINE INDENT if i == 0 or w == 0 : NEW_LINE INDENT K [ i ] [ w ] = 0 NEW_LINE DEDENT elif wt [ i - 1 ] <= w : NEW_LINE INDENT K [ i ] [ w ] = max ( val [ i - 1 ] + K [ i - 1 ] [ w - wt [ i - 1 ] ] , K [ i - 1 ] [ w ] ) NEW_LINE DEDENT else : NEW_LINE INDENT K [ i ] [ w ] = K [ i - 1 ] [ w ] NEW_LINE DEDENT DEDENT DEDENT res = K [ n ] [ W ] NEW_LINE print ( res ) NEW_LINE w = W NEW_LINE for i in range ( n , 0 , - 1 ) : NEW_LINE INDENT if res <= 0 : NEW_LINE INDENT break NEW_LINE DEDENT if res == K [ i - 1 ] [ w ] : NEW_LINE INDENT continue NEW_LINE DEDENT else : NEW_LINE INDENT print ( wt [ i - 1 ] ) NEW_LINE res = res - val [ i - 1 ] NEW_LINE w = w - wt [ i - 1 ] NEW_LINE DEDENT DEDENT DEDENT val = [ 60 , 100 , 120 ] NEW_LINE wt = [ 10 , 20 , 30 ] NEW_LINE W = 50 NEW_LINE n = len ( val ) NEW_LINE printknapSack ( W , wt , val , n ) NEW_LINE