Source code online books for professionals by professionals

Figure 8-5.  The underlying DAG of the LCS problem, where horizontal and vertical edges have zero cost. The longest 
path (that is, the one with the most diagonals) from corner to corner, where the diagonals represent the LCS, is 
highlighted

---

Chapter 8 
■
 tangled dependenCies and MeMoization 
178
The Knapsack Strikes Back
In Chapter 7, I promised to give you a solution to the integer knapsack problem, both in bounded and unbounded 
versions. It’s time to make good on that promise.
Recall that the knapsack problem involves a set of objects, each of which has a weight and a value. Our knapsack 
also has a capacity. We want to stuff the knapsack with objects such that (1) the total weight is less than or equal to 
the capacity, and (2) the total value is maximized. Let’s say that object i has weight w[i] and value v[i]. Let’s do the 
unbounded one first—it’s a bit easier. This means that each object can be used as many times as you want.
I hope you’re starting to see a pattern emerging from the examples in this chapter. This problem fits the pattern 
just fine: We need to somehow define the subproblems, relate them to each other recursively, and then make sure we 
compute each subproblem only once (by using memoization, implicitly or explicitly). The “unboundedness” of the 
problem means that it’s a bit hard to restrict the objects we can use, using the common “in or out” idea (although we’ll 
use that in the bounded version). Instead, we can simply parametrize our subproblems using—that is, use induction 
over—the knapsack capacity.
If we say that m(r) is the maximum value we can get with a (remaining) capacity r, each value of r gives us a 
subproblem. The recursive decomposition is based on either using or not using the last unit of the capacity. If we don’t 
use it, we have m(r) = m(r-1). If we do use it, we have to choose the right object to use. If we choose object i (provided 
it will fit in the remaining capacity), we would have m(r) = v[i] + m(r-w[i]), because we’d add the value of i, but we’d 
also have used up a portion of the remaining capacity equal to its weight.
We can (once again) think of this as a decision process: We can choose whether to use the last capacity unit, 
and if we do use it, we can choose which object to add. Because we can choose any way we want, we simply take 
the maximum over all possibilities. The memoization takes care of the exponential redundancy in this recursive 
definition, as shown in Listing 8-10.