dynamic programming figure decision tree for knapsack problem the root of the tree (node has label indicating that no items have been takenall items remain to be consideredthe value of the items taken is and weight of is still available node indicates that has been taken[ , ,dremain to be consideredthe value of the items taken is and the knapsack can hold another pounds there is no node to the left of node since item bwhich weighs poundswould not fit in the knapsack in figure the numbers that precede the colon in each node indicate one order in which the nodes could be generated this particular ordering is called left-first depth-first at each node we attempt to generate left node if that is impossiblewe attempt to generate right node if that too is impossiblewe back up one node (to the parentand repeat the process eventuallywe find ourselves having generated all descendants of the rootand the process halts when the process haltseach combination of items that could fit in the knapsack has been generatedand any leaf node with the greatest value represents an optimal solution notice that for each leaf nodeeither the second element is the empty list (indicating that there are no more items to consider takingor the fourth element is (indicating that there is no room left in the knapsackunsurprisingly (especially if you read the previous the natural implementation of depth-first tree search is recursive figure contains such an implementation it uses class item from figure the function maxval returns two valuesthe set of items chosen and the total value of those items it is called with two argumentscorresponding to the second and fourth elements of the labels of the nodes in the treetoconsider those items that nodes higher up in the tree (corresponding to earlier calls in the recursive call stackhave not yet considered avail the amount of space still available