Algorithms For Dummies

  Relying on Dynamic Programming 

     311

You may be curious to know what happened inside the memoization dictionary:

print (len(memo))

147

print (memo[2, 10])

([0, 1, 2], 10)

It contains 147 subproblems. In fact, six items multiplied by 21 knapsacks is 126 

solutions, but you have to add another 21 naive solutions to allow the algorithm to 

work properly (naive means leaving the knapsack empty), which increases the 

number of subproblems to 147.

You may find solving 147 subproblems daunting (even though they’re blazingly 

fast to solve). Using brute force alone to solve the problem means solving fewer 

subproblems in this particular case. Solving fewer subproblems requires less time, 

a fact you can test by solving the accounts using Python and the 

comb

 function:

from scipy.misc import comb

objects = 6

np.sum([comb(objects,k

+1) for k in range(objects)])

It takes testing 63 combinations to solve this problem. However, if you try using 

more objects, say, 20, running times look much different because there are now 

1,048,575 combinations to test. Contrast this huge number with dynamic pro-

gramming, which requires solving just 20*21+21 = 441 subproblems.

This  is  the  difference  between  quasi-polynomial  and  exponential  time.  (As  a 

reminder, the book discusses exponential complexity in Chapter 2 when illustrat-

ing the Big O Notation. In Chapter 15, you discover polynomial time as part of the 

discussion about NP complete problems.) Using dynamic programming becomes 

fruitful when your problems are complex. Toy problems are good for learning but 

they can’t demonstrate the full extent of employing smart algorithm techniques 

such as dynamic programming. Each solution tests what happens after adding a 

certain item when the knapsack has a certain size. The preceding example adds 

item 2 (weight=4, value=3) and outputs a solution that puts items 0, 1, and 2 into 

the knapsack (total weight 9 kg) for a value of 10. This intermediate solution 

leverages previous solutions and is the basis for many of the following solutions 

before the algorithm reaches its end.

---

312