Source code online books for professionals by professionals

Listing 8-10.  A Memoized Recursive Solution to the Unbounded Integer Knapsack Problem
def rec_unbounded_knapsack(w, v, c):            # Weights, values and capacity
    @memo                                       # m is memoized
    def m(r):                                   # Max val. w/remaining cap. r
        if r == 0: return 0                     # No capacity? No value
        val = m(r-1)                            # Ignore the last cap. unit?
        for i, wi in enumerate(w):              # Try every object
            if wi > r: continue                 # Too heavy? Ignore it
            val = max(val, v[i] + m(r-wi))      # Add value, remove weight
        return val                              # Max over all last objects
    return m(c)                                 # Full capacity available
 
The running time here depends on the capacity and the number of objects. Each memoized call m(r) is 
computed only once, which means that for a capacity c, we have 
Θ(c) calls. Each call goes through all the n objects, 
so the resulting running time is 
Θ(cn). (This will, perhaps, be easier to see in the equivalent iterative version, coming 
up next. See also Exercise 8-14 for a way of improving the constant factor in the running time.) Note that this is not a 
polynomial running time because c can grow exponentially with the actual problem size (the number of bits).  
As mentioned earlier, this sort of running time is called pseudopolynomial, and for reasonably sized capacities, the 
solution is actually quite efficient.
Listing 8-11 shows an iterative version of the algorithm. As you can see, the two implementations are virtually 
identical, except that the recursion is replaced with a for loop, and the cache is now a list.
14
14
You could preallocate the list, with m = [0]*(c+1), if you prefer, and then use m[r] = val instead of the append.

---

Chapter 8 
■
 tangled dependenCies and MeMoization 
179