# DP Part II

PDF of Eric’s handwritten notes are here.

More Dynamic Programming

Knapsack

Input: $n$ objects with integer weights $w_1, \ldots, w_n$ and integer values $v_1, \ldots, v_n$, and a total capacity $B$.

Output: The set $S$ of objects where $\sum_{i \in S} w_i \le B$ that maximizes $\sum_{i \in S} v_i$.

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

Attempt 1: Look at the prefix of input

For $0\leq i\leq n$, let $T(i)$ be the max value attainable using subset of objects $1,\dots,i$. How to write a recurrence for $T(i)$?

To get optimal solution for $T(i)$, we might add $i$ to $T(i-1)$ or we might take a suboptimal but lighter solution for $1,\dots,i-1$ and add $i$ to it. So need optimal solution for given capacity.

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

For all $0\leq i\leq n$ and all $0\leq b\leq B$, let
$T(i,b) =$ max value attainable from subset of $1, \ldots, i$ and total weight $\leq b$.

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

If $w_i \le b$, then:
$T(i,b) = \max\left\{v_i + T(i-1,b-w_i), T(i-1,b)\right\}$.

Else if $w_i > b$, then:
$T(i,b) = T(i-1,b)$.

Output: Return $T(n,B)$.

Pseudocode:

$KNAPSACK(B, w_1, \ldots, w_n, v_1, \ldots, v_n)$

• for $b = 0\rightarrow B$
• $T(0,b) = 0$
• for $i=1\rightarrow n$
• for $b=1\rightarrow B$
• if $w_i \le b$, then:
$T(i,b) = \max\{v_i + T(i-1,b-w_i),T(i-1,b)\}$
• else if $w_i > b$, then:
$T(i,b)=T(i-1,b)$
• return $T(n,B)$

Running time: The running time is $O(nB)$ since there are $O(nB)$ subproblems and each considers $O(1)$ subproblems.

Version 2: unlimited supply of each item

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

Let $T(b) =$ max value attainable using capacity $\le b$.

Recursive step:
We consider all possibilities for the last item $i$ to add in. If item $i$ fits then we gain value $v_i$ and we take the optimal solution for the remaining capacity of $b-w_i$. Thus, for $0\leq b\leq B$ let:
$T(b) = \max_{1 \le i \le n} \left\{v_i + T(b-w_i) : w_i\leq b, \right\}$.

Output: $T(B)$

Pseudocode:

$KNAPSACK-repeat(B, w_1, \ldots, w_n, v_1, \ldots, v_n)$

• for $b=1\rightarrow B$
• T(b) = 0
• for $i=1\rightarrow n$
• if $w_i \le b$, then:
$T(b) = \max\{T(b),v_i + T(b-w_i)\}$
• return $T(B)$

Running time: The running time of is again $O(nB)$ since there are $O(B)$ subproblems and each considers adding each of the $n$ elements.

Side note:  We will later see that Knapsack is NP-complete.  We’ve just shown an $O(nB)$ time algorithm for Knapsack.  Have we shown a polynomial-time algorithm for an NP-complete problem?  If we did that would imply that $P=NP$ 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 $O( \log B)$ 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 $A,B,C,D$, want to compute $A \times B \times C \times D$ most efficiently.

Say the size of $A$ is $50 \times 20$, $B$ is $20 \times 1$, $C$ is $1 \times 10$, $D$ is $10 \times 100$. There are various ways to compute $A \times B \times C \times D$. The standard approach is to do $(((A \times B) \times C) \times D)$ but we could also do $((A \times B) \times (C \times D))$ or $(A \times (B \times (C \times D))$. There are many possibilities, which way is best?

For a matrix $Y$ of size $a\times b$ and $Z$ of size $b\times c$, consider $W=Y\times Z$ which is of size $a\times c$. Computing an entry of $W$ 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 $Y\times Z$ as abc.

Now we can return to our earlier example and compute the cost for a few different ways of computing $A \times B \times C \times D$:
$((A \times B) \times C) \times D$ has cost $(50)(20)(1)+(50)(1)(10)+(50)(10)(100)=51500$

$(A \times B) \times (C \times D)$ has cost $(50)(20)(1)+(1)(10)(100)+(50)(1)(100)=7000$

$A \times ((B \times C) \times D)$ has cost $(20)(1)(10)+(20)(10)(100)+(50)(20)(100)=120200$

General problem:

Consider matrices $A_1, A_2, \dots, A_n$ where $A_i$ has size $m_{i-1} \times m_i$, what is the minimum cost of computing $A_1\times A_2\times \dots A_n$?

Input: $m_0, m_1, \dots, m_n$

Output: the minimum cost for computing $A_1\times A_2\times \dots A_n$.

First attempt – Use prefixes:

Let $C(i) =$ min cost for computing $A_1 \times \dots \times A_i$

$A_1 \times \dots \times A_i$ splits into $A_1\times A_j$ and $A_{j+1} \times \dots \times A_i$ for some $j$. The min cost for computing $A_1\times A_j$ is $T(j)$, but $A_{j+1} \times \dots \times A_i$ 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 $C(i,j) =$ min cost for multiplying $A_i \times \dots \times A_j$

Recursive solution:
We try all possibilities for the last split. Let $k$ denote the position of the last split so that we are multiplying $A_i\times \cdots\times A_k$ and $A_{k+1}\times \cdots\times A_j$ where $i\leq k < j$. Thus we have the following recurrence:
$C(i,j) = min_{i \le k \le j-1} \{C(i,k) + C(k+1,j) + m_{i-1} m_k m_j\}$

Filling the table:
We have to be more careful now about filling the table. The base case are subproblems where $i=j$ which are the entries $C(i,i)$. Thus we begin by filling the diagonal of the matrix $C$. We then do the case $j=i+1$ which is the off-diagonal of $C$. Thus let $s=j-i$ 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 $\leq s-1$. Thus we fill the table $C$ by $s=0\rightarrow n-1$. For $s=n-1$ we have $i=1, j=n$ which is our final solution $C(1,n)$. We can now state the pseudocode for our algorithm.

$ChainMultiply(m_0, m_1, \dots, m_n)$

• for $i=1$ to $n: C(i,i) = 0$
• for $s=1$ to $n-1:$
• for $i=1$ to $n-s:$
• Let $j = i+s$
• Let $C(i,j) = \infty$
• for $\ell=i$ to $j-1:$
• Let $curr = C(i,\ell) + C(\ell+1,j) + m_{i-1} m_\ell m_j$
• if $curr < C(i,j)$ then let $C(i,j) = curr$
• return $C(1,n)$

Running time: The algorithm has 3 for loops, each of size $O(n)$, and hence the overall running time is $O(n^3)$.