dynamic programming number of calls number of items selected , , , , len(items figure performance of dynamic programming solution the growth is hard to quantifybut it is clearly far less than exponential but how can this besince we know that the / knapsack problem is inherently exponential in the number of itemshave we found way to overturn fundamental laws of the universenobut we have discovered that computational complexity can be subtle notion the running time of fastmaxval is governed by the number of distinct pairs generated this is because the decision about what to do next depends only upon the items still available and the total weight of the items already taken the number of possible values of toconsider is bounded by len(itemsthe number of possible values of avail is more difficult to characterize it is bounded from above by the maximum number of distinct totals of weights of the items that the knapsack can hold if the knapsack can hold at most items (based on the capacity of the knapsack and the weights of the available items)avail can take on at most different values in principlethis could be rather large number howeverin practiceit is not usually so large even if the knapsack has large capacityif the weights of the items are chosen from reasonably small set of possible weightsmany sets of items will have the same total weightgreatly reducing the running time this algorithm falls into complexity class called pseudo polynomial careful explanation of this concept is beyond the scope of this book roughly speakingfastmaxval is exponential in the number of bits needed to represent the possible values of avail since , , , , , , , , , , , , ok"discoveredmay be too strong word people have known this for long time you probably figured it out around