Dynamic Programming
Dynamic Programming
Dr Timothy Kimber
February 2018
Rod Cutting Problem
Back To Solving Problems
The Rod Cutting Problem
A business buys steel rods in a variety of lengths
They will cut the rods into smaller pieces to sell on
Each rod size has a different market value
What is the maximum revenue R(N) for a rod of length N?
Is p(3) + p(3) + p(3) + p(1) > p(4) + p(4) + p(2) ?
Algorithms (580) Dynamic Programming February 2018 2 / 21
Rod Cutting Problem
Instance of The Problem
If the selling prices for each size of rod up to 10 are
size 1 2 3 4 5 6 7 8 9 10
price 3 4 6 9 16 20 22 24 26 30
Then the answer for N = 10 is 32 (1× 6 + 4× 1, or 2× 5)
Algorithms (580) Dynamic Programming February 2018 3 / 21
Rod Cutting Problem
Rod Cutting
size 1 2 3 4 5 6 7 8 9 10
price 3 4 6 9 16 20 22 24 26 30
Question
Given an array of prices P = [P1, . . . ,Pk ] and an integer N between 1 and
k , how can R(N) be computed?
Algorithms (580) Dynamic Programming February 2018 4 / 21
Rod Cutting Problem Analysis
Design
size 1 2 3 4 5 6 7 8 9 10
price 3 4 6 9 16 20 22 24 26 30
Possible outline:
Choose some sizes s = 〈s1, . . . , sj〉 that sum to N
(Values can repeat in s)
Compute Rs = P[s1] + · · ·+ P[sj ]
For all possible s
Update current best R(N) as you go
Algorithms (580) Dynamic Programming February 2018 5 / 21
Rod Cutting Problem Analysis
Design
size 1 2 3 4 5 6 7 8 9 10
price 3 4 6 9 16 20 22 24 26 30
Question
How do you generate (only) sequences s that sum to N?
At this point it will be useful to think about reducing the problem to
solving one or more smaller subproblems.
Algorithms (580) Dynamic Programming February 2018 6 / 21
Rod Cutting Problem Analysis
Design
size 1 2 3 4 5 6 7 8 9 10
price 3 4 6 9 16 20 22 24 26 30
Choosing sizes:
Pick an s1
Then s is s1 followed by 〈s2, . . . 〉 that sum to N − s1
Can now see the structure of the problem:
For each possible s1
Find all solutions for N − s1, and combine with s1
Base case: only sequence that sums to 0 is 〈〉
Algorithms (580) Dynamic Programming February 2018 7 / 21
Rod Cutting Problem Analysis
Design
size 1 2 3 4 5 6 7 8 9 10
price 3 4 6 9 16 20 22 24 26 30
Re-evaluate overall design:
Pick an s1
Max revenue using s1 is P[s1] + R(N − s1)
R(N − s1) is overall solution for rod length (N − s1)
One option per value for s1
Algorithms (580) Dynamic Programming February 2018 8 / 21
Rod Cutting Simple Algorithm
A Simple Recursive Solution
SimpleRodCut(Input: N, P = [P1, . . . ,Pk ])
if N == 0
return 0
else
for i = 1 to N
choices[i] = P[i] + SimpleRodCut(N-i, P)
return max(choices)
choices collects total for each s1
max finds the maximum of the choices
How does this run?
Algorithms (580) Dynamic Programming February 2018 9 / 21
Rod Cutting Simple Algorithm
Simple Rod Cut — Reflection
WOW that was sloooooowww.
Question
Solving R(0) takes Θ(1) time. What about R(N)?
Algorithms (580) Dynamic Programming February 2018 10 / 21
Rod Cutting Time
Time for Simple Solution
The time taken by SimpleRodCut is
T (0) = Θ(1)
T (N) = 2T (N − 1) + Θ(1), for N > 0
or
T (N) = 2N−1T (0) + Θ(1)
so T (N) = Θ(2N).
The running time grows exponentially.
This is not a practical solution.
Algorithms (580) Dynamic Programming February 2018 11 / 21
Other Strategies Divide & Conquer
Divide & Conquer?
Can we divide the problem? (and conquer?)
size 1 2 3 4 5 6 7 8 9 10
price 3 4 6 9 16 20 22 24 26 30
Algorithms (580) Dynamic Programming February 2018 12 / 21
Other Strategies Dynamic Programming
New Strategy
What is there that we can take advantage of?
The subproblems overlap
Algorithms (580) Dynamic Programming February 2018 13 / 21
Other Strategies Dynamic Programming
Dynamic Programming
Dynamic Programming makes a space–time tradeoff
Do not want to recompute the answer to R(i) every time
Compute it once and save the answer in a table
Check the table before computing each subproblem
This is called memoisation (we are making a note for later)
MemoisedRodCut(Input: N, P = [P1, . . . ,Pk ])
for i = 0 to N
R[i] = 0
return MemoiseAux(N, P, R)
R is the table to be filled in
Algorithms (580) Dynamic Programming February 2018 14 / 21
Other Strategies Dynamic Programming
Memoisation
MemoiseAux(Input: N, P = [P1, . . . ,Pk ], R = [R0, . . . ,RN′ ])
if N == 0
return 0
if R[N] > 0
return R[N]
for i = 1 to N
choices[i] = P[i] + MemoiseAux(N-i, P, R)
R[N] = max(choices)
return R[N]
If R[N] was already computed (R[N] > 0) it is returned immediately
Otherwise we compute it, save it, and then return it
Also called Top Down (set out to solve the biggest problem)
Algorithms (580) Dynamic Programming February 2018 15 / 21
Other Strategies Dynamic Programming
The ‘Bottom Up’ Method
We know which problems depend on which others
so we can just complete the table in order
this will be more efficient than recursion
BottomUpRodCut(Input: N, P = [P1, . . . ,Pk ])
R[0] = 0
for i = 1 to N
choices = [0,…,0]
for j = 1 to i
choices[j] = P[j] + R[i-j]
R[i] = max(choices)
return R[N]
What is the running time?
Algorithms (580) Dynamic Programming February 2018 16 / 21
Dynamic Programming Properties
Dynamic Programming
Dynamic programming can be applied to a problem if
The problem has optimal substructure
The problem has overlapping subproblems
A problem has optimal substructure if
the problem can be decomposed into subproblems
an optimal solution uses optimal solutions to the subproblems
In rod cutting the optimal solution for N was one of
P[i ] + R[N − i ], where 1 ≤ i < N and each R[N − i ] was an optimal solution for N − i . Algorithms (580) Dynamic Programming February 2018 17 / 21 Dynamic Programming Optimal Substructure Optimal Substructure Problems may appear to have optimal substructure when they do not Problem (Unweighted Shortest Path) Input: graph G = (V ,E ). Input: vertices u, v ∈ V . Output: the simple path from u to v containing the fewest edges Problem (Unweighted Longest Path) Input: graph G = (V ,E ). Input: vertices u, v ∈ V . Output: the simple path from u to v containing the most edges Algorithms (580) Dynamic Programming February 2018 18 / 21 Dynamic Programming Optimal Substructure Optimal Substructure A shortest path is composed of optimal solutions to subproblems The shortest path from 1 to 2 (via x) is shortest path from 1 to x plus the shortest path from x to 2 Algorithms (580) Dynamic Programming February 2018 19 / 21 Dynamic Programming Optimal Substructure Optimal Substructure How about a longest path? Independent subproblem solutions do not make an optimal solution In an optimal solution the subproblems will interfere Algorithms (580) Dynamic Programming February 2018 20 / 21 Dynamic Programming Overlapping Problems Overlapping Subproblems The second property we need when applying dynamic programming is overlapping subproblems The same problems are generated over and over The subproblems must still be independent The set of all subproblems is the subproblem space The smaller the subproblem space the quicker the (dynamic) algorithm Algorithms (580) Dynamic Programming February 2018 21 / 21 Rod Cutting Problem Problem Analysis Simple Algorithm Time Other Strategies Divide & Conquer Dynamic Programming Dynamic Programming Properties Optimal Substructure Overlapping Problems