notice that the implementation of maxval does not build the decision tree and then look for an optimal node insteadit uses the local variable result to record the best solution found so far def maxval(toconsideravail)"""assumes toconsider list of itemsavail weight returns tuple of the total weight of solution to the / knapsack problem and the items of that solution""if toconsider =[or avail = result ( ()elif toconsider[ getweight(avail#explore right branch only result maxval(toconsider[ :]availelsenextitem toconsider[ #explore left branch withvalwithtotake maxval(toconsider[ :]avail nextitem getweight()withval +nextitem getvalue(#explore right branch withoutvalwithouttotake maxval(toconsider[ :]avail#choose better branch if withval withoutvalresult (withvalwithtotake (nextitem,)elseresult (withoutvalwithouttotakereturn result def smalltest()names [' '' '' '' 'vals [ weights [ items [for in range(len(vals))items append(item(names[ ]vals[ ]weights[ ])valtaken maxval(items for item in takenprint item print 'total value of items taken ='val figure using decision tree to solve knapsack problem when smalltest (which uses the values in figure is run it prints result indicating that node in figure is an optimal solutiontotal value of items taken if you run this code on any of the examples we have looked atyou will find that it produces an optimal answer in factit will always produce an optimal answerif it gets around to producing any answer at all the code in figure makes it convenient to test maxval it randomly generates list of items of specified size try bigtest( now try