Source code online books for professionals by professionals

Listing 8-12.  A Memoized Recursive Solution to the 0-1 Knapsack Problem
def rec_knapsack(w, v, c):                      # Weights, values and capacity
    @memo                                       # m is memoized
    def m(k, r):                                # Max val., k objs and cap r
        if k == 0 or r == 0: return 0           # No objects/no capacity
        i = k-1                                 # Object under consideration
        drop = m(k-1, r)                        # What if we drop the object?
        if w[i] > r: return drop                # Too heavy: Must drop it
        return max(drop, v[i] + m(k-1, r-w[i])) # Include it? Max of in/out
    return m(len(w), c)                         # All objects, all capacity
 
In a problem such as LCS, simply finding the value of a solution can be useful. For LCS, the length of the longest 
common subsequence gives us an idea of how similar two sequences are. In many cases, though, you’d like to find 
the actual solution giving rise to the optimal cost. The iterative knapsack version in Listing 8-13 constructs an extra 
table, called P because it works a bit like the predecessor tables used in traversal (Chapter 5) and shortest path 
15
The object index i = k-1 is just a convenience. We might just as well write m(k,r) = v[k-1] + m(k-1,r-w[k-1]).

---

Chapter 8 
■
 tangled dependenCies and MeMoization 
180
algorithms (Chapter 9). Both versions of the 0-1 knapsack solutions have the same (pseudopolynomial) running time 
as the unbounded ones, that is, 
Θ(cn).