PDF of Eric’s handwritten notes are here.

More Dynamic Programming: **Knapsack** (with and without repetition) and **chain matrix multiplication**

**Knapsack**

Input: objects with integer weights and integer values , and a total capacity .

Output: The set of objects where that maximizes .

**Version 1: can only include an item at most once.**

**Attempt 1: **Look at the prefix of input

For , let be the max value attainable using subset of objects . How to write a recurrence for ?

To get optimal solution for , we might add to or we might take a suboptimal but lighter solution for and add to it. So need optimal solution for given capacity.

**Attempt 2: **Take prefix of objects & “prefix” of capacity.

For all and all , let

max value attainable from subset of and total weight .

**Recursive step**: We’ll decide whether to include item or not. There are two cases depending on whether or not item fits the current capacity.

If , then:

.

Else if , then:

.

**Output**: Return .

**Pseudocode**:

- for
- for
- for
- if , then:

- else if , then:

- if , then:

- for
- return

**Running time**: The running time is since there are subproblems and each considers subproblems.

**Version 2: unlimited supply of each item**

Now we don’t need to keep track of which objects are used so far.

Let max value attainable using capacity .

**Recursive step**:

We consider all possibilities for the last item to add in. If item fits then we gain value and we take the optimal solution for the remaining capacity of . Thus, for let:

.

**Output: **

**Pseudocode**:

- for
- T(b) = 0
- for
- if , then:

- if , then:

- return

**Running time**: The running time of is again since there are subproblems and each considers adding each of the elements.

**Side note: **We will later see that Knapsack is NP-complete. We’ve just shown an time algorithm for Knapsack. Have we shown a polynomial-time algorithm for an NP-complete problem? If we did that would imply that so what’s the catch since *nB* is a polynomial in *n* and *B? *The catch is that it is not polynomial in the input size. The total capacity *B* is a single number. How big is the input for this parameter? It takes bits to express *B*. Thus to be polynomial in the input size the running time of our algorithm should be polynomial in *n* and *logB*. So our current algorithm is actually exponential in the input size.

**Chain matrix multiply**

Example: Given 4 matrices , want to compute most efficiently.

Say the size of is , is , is , is . There are various ways to compute . The standard approach is to do but we could also do or . There are many possibilities, which way is best?

For a matrix of size and of size , consider which is of size . Computing an entry of involves *b* multiplications and *b-1* additions. Since there are *ac* entries of *W*, in total there are *abc* multiplications and *a(b-1)c* additions. To simplify (and since multiplications take longer than additions) let us define the cost of computing as *abc*.

Now we can return to our earlier example and compute the cost for a few different ways of computing :

has cost

has cost

has cost

**General problem:**

Consider matrices where has size , what is the minimum cost of computing ?

Input:

Output: the minimum cost for computing .

**First attempt – Use prefixes:**

Let min cost for computing

splits into and for some . The min cost for computing is , but does not correspond to a prefix so we can’t look up its solution in our table. Thus prefixes don’t work, but we have an idea for what to try next: substrings.

**Second attempt – Use substrings:**

**Subproblem definition:**

Let min cost for multiplying

**Recursive solution:**

We try all possibilities for the last split. Let denote the position of the last split so that we are multiplying and where . Thus we have the following recurrence:

**Filling the table:**

We have to be more careful now about filling the table. The base case are subproblems where which are the entries . Thus we begin by filling the diagonal of the matrix . We then do the case which is the off-diagonal of . Thus let which we can view as the width of the subproblem. Note that to solve a subproblem with width *s* we need to consider subproblems of width . Thus we fill the table by . For we have which is our final solution . We can now state the pseudocode for our algorithm.

- for to
- for to
- for to
- Let
- Let
- for to
- Let
- if then let

- for to

- for to
- return

**Running time:** The algorithm has 3 for loops, each of size , and hence the overall running time is .