record cut rod solutions

1 files changed, 102 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index 7598d56..a857010 100644
--- a/notes.md
+++ b/notes.md
@@ -1522,3 +1522,105 @@ combining solutions to subproblems.
 Divide and conquer algorithms partition the problem into disjoint subproblems,
 solve the subproblems recursively, and then combine their solutions to solve the
 original problem.
+
+Is like recursivion but also when the subproblems overlap so we don't have to
+recompute the same answer over and over.
+We save answers to a table to avoid recompute.
+It applies to optimization problems.
+
+* it can have many solutions
+* wish to find optimal solution
+* "an" optimal solution not "the" solution.
+
+Steps:
+
+1. characterize the structure of an optimal solution
+1. recursively define the value of an optimal solution
+1. compute the value of "an" optimal solution. (bottom-up)
+1. construct optimal solution from computed information.
+
+15.1
+
+Rod-cutting Problem
+
+Where to cut steel rods to make the most revenue?
+* cuts are free
+* i = 1,2,... to price pi in $ for length i
+
+given a rod of length n inches and a table of prices pi for i = 1,2...n
+determine the max revenue rn obtainable by cutting up the rods and selling
+pieces if pn for a rod is length n is large enough, no cutting might be
+necessary.
+
+Recursive top down approach: exponential time 2^n
+
+```plaintext
+CUT-ROD(p, n)
+  if n == 0
+    return 0
+  q = -1
+  for i = 1 to n
+    q = max(q, p[i] + CUT-ROD(p, n-1))
+  return q
+```
+
+DP - time-memory trade-off.
+* exponential solution might be turned into polynomial solution.
+
+TOP down solution:
+```plaintext
+MEMOIZED-CUT-ROD(p, n)
+  let r[0..n] be a new array
+  for i = 0 to n
+    r[i] = -1
+  return MEMOIZED-CUT-ROD-AUX(p, n, r)
+
+MEMOIZED-CUT-ROD-AUX(p, n, r)
+  return r[n] if r[n] >= 0
+  return 0 if n == 0
+
+  for i = 1 to n
+    q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-1, r)
+  r[n] = q
+
+  return q
+```
+
+BOTTOM up solution:
+
+```plaintext
+BOTTOM-UP-CUT-ROD(p, n)
+  let r[0..n] be a new array
+  r[0] = 0
+
+  for j = 1 to n
+    q = -1
+    for i = 1 to j
+      q = max(q, p[i] + r[j - i])
+
+  r[j] = q
+  return r[n]
+```
+
+Extended solution that prints max revenue and the # of cuts needed for each
+length to produce that revenue.
+
+```plaintext
+EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
+  let r = [0..n]
+  let s = [1..n]
+  r[0] = 0
+  for j = 1 to n
+    q = -1
+    for i = 1 to j
+      if q < p[i] + r[j-1]
+        q = p[i] + r[j-1]
+        s[j] = i
+    r[j] = q
+  return r, s
+PRINT-CUT-ROD-SOLUTION(p,n)
+  (r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
+  while n > 0
+    print s[n]
+    n = n - s[n]
+```