dynamic programming bigtest( after you get tired of waiting for it to returnstop it and ask yourself what is going on def buildmanyitems(numitemsmaxvalmaxweight)items [for in range(numitems)items append(item(str( )random randint( maxval)random randint( maxweight))return items def bigtest(numitems)items buildmanyitems(numitems valtaken maxval(items print 'items takenfor item in takenprint item print 'total value of items taken ='val figure testing the decision tree-based implementation let' think about the size of the tree we are exploring since at each level of the tree we are deciding to keep or not keep one itemthe maximum depth of the tree is len(itemsat level we have only one nodeat level up to two nodesat level up to four nodesat level up to eight nodes at level we have up to nodes no wonder it takes long time to runwhat should we do about thislet' start by asking whether this program has anything in common with our first implementation of fibonacci in particularis there optimal substructure and are there overlapping subproblemsoptimal substructure is visible both in figure and in figure each parent node combines the solutions reached by its children to derive an optimal solution for the subtree rooted at that parent this is reflected in figure by the code following the comment #choose better branch are there also overlapping subproblemsat first glancethe answer seems to be "no at each level of the tree we have different set of available items to consider this implies that if common subproblems do existthey must be at the same level of the tree and indeed at each level of the tree each node has the same set of items to consider taking howeverwe can see by looking at the labels in figure that each node at level represents different set of choices about the items considered higher in the tree think about what problem is being solved at each node the problem being solved is finding the optimal items to take from those left to considergiven the remaining available weight the available weight depends upon the total weight of the items takenbut not on which items are taken or the total value of the items taken sofor examplein figure nodes and are actually solving the same problemdeciding which elements of [ ,dshould be takengiven that the available weight is