Knapsack Chain Multiply

Summary

When attempting to solve problems via dynamic programming, it is often useful to first try solving a subproblem that is a prefix of the main problem. If that doesn’t work, you can try a substring.

Contents

• Knapsack Problem
  • Without Repition
    • Attempt 1
    • Attempt 2
  • With Repition
    • Simpler Subproblem
• Chain Matrix Multiply
  • Graphical View
  • Attempt 1
  • Substrings
    • Psuedocode
• Compute diagonally
• Practice Problems

Knapsack Problem

Input: n objects with a weight and a value, and a total capacity.

Goal: Find a subset of objects that fit in the knapsack and maximizes the total value

There are two versions:

• One copy of each object
  • “without repitition”
• Unlimited copy of each object
  • “with repitition”

Without Repition

A greedy approach often fails, so we need to maintain sub-optimal solutions along the way

Attempt 1

1. K(i) = max value achievable using a subset of objects 1 through i
2. Express K(i) in terms of K(1) through K(i-1)

Given:

$\begin{aligned} \text{values} &= 15, 10, 8, 1 \ \text{weights} &= 15, 12, 10, 5 \ \text{k} &= 15, 15, 18, 18 \end{aligned}$

The $i = 2$ solution doesn’t depend on the $i = 1$ solution. We need to maintain a sub-optimal solution for $i = 1$. We need to maintain $\text{capacity} \le B - w_i$. This meains we need to change the subproblem definition to say we are including object i.

Attempt 2

1. $\text{For } i & b \text{ where } 0 \le i \le n & 0 \le b \le B: \text{ let } k(i,b) =$ a max value achievable using a subset of objects 1 through i and a total weight of b
2. Express K(i) in terms of K(1) through K(i-1)

if $w_i \le b$:

$K(i,b) = \max{\lbrace v_i + K(i-1, b-w_i), K(i-1,b) \rbrace}$

That is to say, if either we include the current object and use the value of the previous best solution that has enough capacity to include the object, or we don’t include the object and use the previous best value.

Knapsack(W,V,B):
  for b in range(0,B):
    K[0][b] = 0
  for i in range(0,N):
    K[i][0] = 0
  for i in range(0,N):
    for b = in range(1,B):
      if W[i] <= b:
        K[i][b] = max(V[i] + K[i-1][b-W[i]], K[i-1][b])
      else:
        K[i][b] = K[i-1][b]
  return K[n][B]

Total runtime is O(nB)

With Repition

1. $\text{For } i & b \text{ where } 0 \le i \le n & 0 \le b \le B: \text{ let } k(i,b) =$ a max value achievable using a multiset of objects 1 through i and a total weight of b
2. Express K(i) in terms of K(1) through K(i-1)

$K(i,b) = \max{ \lbrace K(i-1,b), v_i + K(i, b-w_i) \rbrace }$

Similar psuedocode

Simpler Subproblem

Do we need parameter i?

$\text{For } b \text{ where } 0 \le b \le B: K(b) =$ max value attainable using weight less than or equal to b

$K(b) = \max_i{ \left\lbrace v_i + K(b-w) : 1 \le i \le n, w_i \le b \right\rbrace}$

KnapsackRepeat(W,V,B):
  for b in range(0,B):
    K[b] = 0
    for i in range(0,n):
      if W[i] <= b && K[b] < V[i] + K[b-W[i]]:
        K[b] = V[i] + K[b-W[i]]
  return K[B]

Runtime is still O(nB), but space is smaller and algo is simpler

Chain Matrix Multiply

Example: 4 matrices, A, B, C, D

Goal: Computer $A \times B \times C \times D$ most efficiently

$\begin{aligned} \lvert A \rvert &= 50 \times 20 \ \lvert B \rvert &= 20 \times 1 \ \lvert C \rvert &= 1 \times 10 \ \lvert D \rvert &= 10 \times 100 \end{aligned}$

$\begin{aligned} ((A \times B) \times C) \times D \ (A \times B) \times (C \times D) \ (A \times (B \times C)) \times D \ A \times (B \times (C \times D)) \end{aligned}$

Which is better? What is the cost?

If a matrix W has size axb and Y a size of bxc, then WxY has a cost of abc

$\begin{aligned} ((A \times B) \times C) \times D &= ((50 \times 20 \times 1) + 50 \times 1 \times 10) + 50 \times 10 \times 100 &= 51,500 \ (A \times B) \times (C \times D) &= (50 \times 20 \times 1) + (1 \times 10 \times 100) + 50 \times 1 \times 100 &= \phantom{4}7,000 \ \vdots \end{aligned}$

Input: N matrices

Goal: What’s the min cost for computing $A_1 \times A_2 \times \cdots \times A_n \text{ where } \lvert A_i \rvert = m_{i-1} \times m_i$

Graphical View

$((A \times B) \times C) \times D$

$(A \times B) \times (C \times D) \$

Attempt 1

We can’t simply use a prefix because some computations are a substring (like $A[i+1] \times \ldots \times A[j]$)

Substrings

$\text{For } i & j \text{ where } 1 \le i \le j \le n$

$\text{let } C(i,j) = \min \text{ cost for computing } A_i \times A_{i+1} \times \cdots \times A_j$

$C(i,j) = \begin{cases} 0 & i = j \ \displaystyle\min_l{\lbrace C(i,l) + C(l+1,j) + m_{i-1}m_lm_j \rbrace} & i \le l \le j-1 \end{cases}$

Psuedocode

NOTE This might be wrong

ChainMultiply(M):
  for i in range(0,n):
    C[i][i] = 0

  # Compute diagonally
  for s in range(1, n-1):
    for i in range(1, n-s):
      j = i+1
      C[i][j] = INF
      for l in range(i, j-1):
        cur = M[i-1] * M[l] * M[j] + C[i][l] + C[l+1][j]
        if C[i][j] > cur:
          C[i][j] = cur

  return C[0][n]

Runtime is $O(n^3)$

Practice Problems

$\begin{aligned} [DPV] & \text{ 6.17 (Change making) } \ & \text{ 6.18 } \ & \text{ 6.19 } \ & \text{ 6.20 (Optimal BST) } \ & \text{ 6.21 (Palindrome sequence/substring) } \end{aligned}$

Try prefix, then substring.

If you do use substring, go back over the recurrence to see all parameters are needed.