diff options
Diffstat (limited to 'notes.md')
| -rw-r--r-- | notes.md | 102 |
1 files changed, 102 insertions, 0 deletions
@@ -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] +``` |