程序代写代做代考 algorithm Dynamic Programming

Dynamic Programming

Dynamic Programming

Dr Timothy Kimber

February 2018

Rod Cutting Problem

Back To Solving Problems

The Rod Cutting Problem

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