Lecture 16: Dynamic Programming – Pole Cutting
COMS10007 – Algorithms
26.03.2019
Lecture 16: Dynamic Programming – Pole Cutting 1 / 17
Copyright By PowCoder代写 加微信 powcoder
Pole Cutting
Pole-cutting:
Given is a pole of length n
The pole can be cut into multiple pieces of integral lengths A pole of length i is sold for price p(i), for some function p
lengthi 1 2 3 4 5 6 7 8 9 10 pricep(i) 1 5 8 9 10 17 17 20 24 30
Lecture 16: Dynamic Programming – Pole Cutting
Pole Cutting (2)
Problem: Pole-Cutting
1 Input: Price table pi , for every i ≥ 1, length n of initial pole
2 Output: Maximum revenue rn obtainable by cutting pole into smaller pieces
How many ways of cutting the pole are there?
Lecture 16: Dynamic Programming – Pole Cutting 3 / 17
Pole Cutting (3)
There are 2n−1 ways to cut a pole of length n.
There are n − 1 positions where the pole can be cut. For each position we either cut or we don’t. This gives 2n−1 possibilities.
Find best out of 2n−1 possibilities
We could diregard similar cuts, but we would still have an
exponential number of possibilites
A fast algorithm cannot try out all possibilities
Lecture 16: Dynamic Programming – Pole Cutting
Pole Cutting (4)
means we cut a pole of length 7 into pieces of lengths 2, 2 and 3
Optimal Cut
Suppose the optimal cut uses k pieces
n = i1 + i2 + · · · + ik
Optimal revenue rn:
rn =p(i1)+p(i2)+···+p(ik)
Lecture 16: Dynamic Programming – Pole Cutting
Pole Cutting (5)
What are the optimal revenues ri?
lengthi 1 2 3 4 5 6 7 8 9 10
pricep(i) 1 5 8 9 10 17 17 20 24 30
r1=1 1=1 r2=5 2=2 r3=8 3=3
r4=10 r5=13 r6=17 r7=18 r8=22 r9=25
4=2+2 5=2+3 6=6 7=2+2+3 8=2+6 9=3+6 10=10
Lecture 16: Dynamic Programming – Pole Cutting 6 / 17
Optimal Substructure
Optimal Substructure
Consider an optimal solution to input length n n = i1 + i2 + · · · + ik for some k
n − i1 = i2 + · · · + ik
is an optimal solution to the problem of size n − i1
Computing Optimal Revenue rn:
rn =max{pn,r1 +rn−1,r2 +rn−2,…,rn−1 +r1}
pn corresponds to the situation of no cut at all
ri + rn−i: initial cut into two pieces of sizes i and n − i
Lecture 16: Dynamic Programming – Pole Cutting
Pole Cutting: Dynamic Programming Formulation
Simpler Recursive Formulation: Let r0 = 0 rn = max (pi + rn−i ) .
Observe: Only one subproblem in this formulation
Example: n = 4
rn = max{p1 + r3,p2 + r2,p3 + r1,p4 + r0}
p1 +r3 p2 +r2 p3 +r1 p4 +r0
Lecture 16: Dynamic Programming – Pole Cutting 8 / 17
Recursive Top-down Implementation
Direct Implementation:
rn = max (pi + rn−i ) and r0 = 0 . 1≤i ≤n
Require: Integer n, Array p of length n with prices if n = 0 then
return 0 q ← −∞
for i = 1 . . . n do
q ← max{q, p[i] + Cut-Pole(p, n − i)}
Algorithm Cut-Pole(p, n) How efficient is this algorithm?
Lecture 16: Dynamic Programming – Pole Cutting 9 / 17
Recursion Tree for Cut-Pole
Example: n = 5
Number Recursive Calls: T(n)
T (n) = 1 + T (j ) and T (0) = 1
Lecture 16: Dynamic Programming – Pole Cutting 10 / 17
Solving Recurrence
How to Solve this Recurrence?
T (n) = 1 + T (j ) and T (0) = 1
Substitution Method: Using guess T(n) = O(cn), for some c Trick: compute T (n) − T (n − 1)
n−1 n−2 T(n)−T(n−1) = 1+T(j)−1+T(j)
j=0 j=0 = T(n−1),hence:
T(n) = 2T(n−1). This implies T(i) = 2i.
Lecture 16: Dynamic Programming – Pole Cutting
Discussion
Runtime of Cut-Pole
Recursion tree has 2n nodes
Each function call takes time O(n) (for-loop)
Runtime of Cut-Pole is therefore O(n2n). (O(2n) can also be argued)
What can we do better?
Observe: We compute solutions to subproblems many times Avoid this by storing solutions to subproblems in a table! This is a key feature of dynamic programming
Lecture 16: Dynamic Programming – Pole Cutting
Implementing the Dynamic Programming Approach
Top-down with memoization
When computing ri , store ri in a table T (of size n)
Before computing ri again, check in T whether ri has previously been computed
Fill table T from smallest to largest index No recursive calls are needed for this
Lecture 16: Dynamic Programming – Pole Cutting
Top-down Approach
Require: Integer n, Array p of length n with prices Let r[0…n] be a new array
for i = 0 . . . n do
return Memoized-Cut-Pole-Aux(p,n,r)
Algorithm Memoized-Cut-Pole(p, n)
Prepare a table r of size n
Initialize all elements of r with −∞
Actual work is done in Memoized-Cut-Pole-Aux, table r is passed on to Memoized-Cut-Pole-Aux
Lecture 16: Dynamic Programming – Pole Cutting
Top-down Approach (2)
Require: Integer n, array p of length n with prices, array r of revenues
if r[n] ≥ 0 then return r[n]
if n = 0 then q←0
for i = 1 . . . n do
q ← max{q, p[i] + Memoized-Cut-Pole-Aux(p, n −
i,r)} r[n] ← q
Algorithm Memoized-Cut-Pole-Aux(p, n, r) Observe: If r[n] ≥ 0 then r[n] has been computed previously
Lecture 16: Dynamic Programming – Pole Cutting 15 / 17
Bottom-up Approach
Require: Integer n, array p of length n with prices Let r[0…n] be a new array
for j = 1 . . . n do
for i = 1 . . . j do
q ← max{q, p[i] + r[j − i]} r[j] ← q
return r[n]
Algorithm Bottom-Up-Cut-Pole(p, n) Runtime: Two nested for-loops
nj nj n n(n+1) O(1) = O(1)1 = O(1)j = O(1) 2 = O(n2) .
j=1 i=1 j=1 i=1 j=1
Lecture 16: Dynamic Programming – Pole Cutting 16 / 17
of Top-down Approach O(n2) (please think about this!)
Dynamic Programming
Solves a problem by combining subproblems
Subproblems are solved at most once, store solutions in table
If a problem exhibits optimal substructure then dynamic programming is often the right choice
Top-down and bottom-up approaches have the same runtime
Lecture 16: Dynamic Programming – Pole Cutting
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com