the code in figure exploits the optimal substructure and overlapping subproblems to provide dynamic programming solution to the / knapsack problem an extra parametermemohas been added to keep track of solutions to subproblems that have already been solved it is implemented using dictionary with key constructed from the length of toconsider and the available weight the expression len(toconsideris compact way of representing the items still to be considered this works because items are always removed from the same end (the frontof the list toconsider def fastmaxval(toconsideravailmemo {})"""assumes toconsider list of itemsavail weight memo used only by recursive calls returns tuple of the total weight of solution to the / knapsack problem and the items of that solution""if (len(toconsider)availin memoresult memo[(len(toconsider)avail)elif toconsider =[or avail = result ( ()elif toconsider[ getweight(avail#explore right branch only result fastmaxval(toconsider[ :]availmemoelsenextitem toconsider[ #explore left branch withvalwithtotake =fastmaxval(toconsider[ :]avail nextitem getweight()memowithval +nextitem getvalue(#explore right branch withoutvalwithouttotake fastmaxval(toconsider[ :]availmemo#choose better branch if withval withoutvalresult (withvalwithtotake (nextitem,)elseresult (withoutvalwithouttotakememo[(len(toconsider)avail)result return result figure dynamic programming solution to knapsack problem figure shows the number of calls made when we ran the code on problems of various sizes