def choosebest(psetmaxweightgetvalgetweight)bestval bestset none for items in psetitemsval itemsweight for item in itemsitemsval +getval(itemitemsweight +getweight(itemif itemsweight bestvalbestval itemsval bestset items return (bestsetbestvaldef testbest(maxweight )items builditems(pset genpowerset(itemstakenval choosebest(psetmaxweightitem getvalueitem getweightprint 'total value of items taken ='val for item in takenprint item figure brute-force optimal solution to the / knapsack problem the complexity of this implementation is ( * )where is the length of items the function genpowerset returns list of lists of items this list is of length nand the longest list in it is of length therefore the outer loop in choosebest will be executed ( ntimesand the number of times the inner loop will be executed is bounded by many small optimizations can be applied to speed this program up for examplegenpowerset could have had the header def genpowerset(itemsconstraintgetvalgetweightand returned only those combinations that meet the weight constraint alternativelychoosebest could exit the inner loop as soon as the weight constraint is exceeded while these kinds of optimizations are often worth doingthey don' address the fundamental issue the complexity of choosebest will still be ( * )where is the length of itemsand choosebest will therefore still take very long time to run when items is large in theoretical sensethe problem is hopeless the / knapsack problem is inherently exponential in the number of items in practical sensehoweverthe problem is far from hopelessas we will discuss in when testbest is runit printstotal value of items taken notice that this solution is better than any of the solutions found by the greedy algorithms the essence of greedy algorithm is making the best (as defined by