《计算模型与算法技术》课程教学资源（PPT讲稿）Chapter 8 Dynamic Programming

Chapter 8 introduction to The Design & Dynamic Programming Analysis of Algorithms 2ND EDITION Anany Levitin PEARSON Addison Wesley Copyright @ 2007 Pearson Addison-Wesley. All rights reserved

Chapter 8 Dynamic Programming Copyright © 2007 Pearson Addison-Wesley. All rights reserved

Dynamic Programming Dynamic Programming is a general algorithm design technique for solving problems defined by or formulated as recurrences with overlapping subinstances Invented by American mathematician Richard Bellman in the 1950s to solve optimization problems and later assimilated by cs °“ Programming” here means" planning” Main idea: set up a recurrence relating a solution to a larger instance to solutions of some smaller instances solve smaller instances once record solutions in a table extract solution to the initial instance from that table Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-1 Dynamic Programming Dynamic Programming is a general algorithm design technique for solving problems defined by or formulated as recurrences with overlapping subinstances • Invented by American mathematician Richard Bellman in the 1950s to solve optimization problems and later assimilated by CS • “Programming” here means “planning” • Main idea: - set up a recurrence relating a solution to a larger instance to solutions of some smaller instances - solve smaller instances once - record solutions in a table - extract solution to the initial instance from that table

Example: Fibonacci numbers Recall definition of fibonacci numbers: F(n)=F(n-1)+F(n=2) F(0)=0 F()=1 Computing the nth Fibonacci number recursively(top-down): F(n-2 F(2)+P(n-3)F(3)+F(n-4 Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-2

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-2 Example: Fibonacci numbers • Recall definition of Fibonacci numbers: F(n) = F(n-1) + F(n-2) F(0) = 0 F(1) = 1 • Computing the nth Fibonacci number recursively (top-down): F(n) F(n-1) + F(n-2) F(n-2) + F(n-3) F(n-3) + F(n-4)

Example: Fibonacci numbers(cont) Computing the nth Fibonacci number using bottom-up iteration and recording results F(0)=0 F(1) F(2)=1+0=1 F(n-2) F(n-1)= F(n)=F(n-1)+F(n-2) 01 F(n-2)F(n-1)F(n) Efficiency: time n What if we solve space n it recursively? Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-3 Example: Fibonacci numbers (cont.) Computing the n th Fibonacci number using bottom-up iteration and recording results: F(0) = 0 F(1) = 1 F(2) = 1+0 = 1 … F(n-2) = F(n-1) = F(n) = F(n-1) + F(n-2) Efficiency: - time - space 0 1 1 . . . F(n-2) F(n-1) F(n) n n What if we solve it recursively?

Examples of DP algorithms Computing a binomial coefficient Longest common subsequence Warshall's algorithm for transitive closure Floyd's algorithm for all-pairs shortest paths Constructing an optimal binary search tree Some instances of difficult discrete optimization problems: traveling salesman knapsack Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-4

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-4 Examples of DP algorithms • Computing a binomial coefficient • Longest common subsequence • Warshall’s algorithm for transitive closure • Floyd’s algorithm for all-pairs shortest paths • Constructing an optimal binary search tree • Some instances of difficult discrete optimization problems: - traveling salesman - knapsack

Computing a binomial coefficient by DP Binomial coefficients are coefficients of the binomial formula: (a+b)=C(n,0)a b0+.+C(n, k)a/-kbk+.+C(n, n)ab" Recurrence: C(,k)=C(n-1, )+C(n-1, k-1) for n>k>0 C(,0)=1,C(,m)=1forn≥0 Value of c(n, k) can be computed by filling a table 012 /-1 (-1,kx-1)C(m-1,k) n Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-5

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-5 Computing a binomial coefficient by DP Binomial coefficients are coefficients of the binomial formula: (a + b) n = C(n,0)a nb 0 + . . . + C(n,k)a n-kb k+ . . . + C(n,n)a 0b n Recurrence: C(n,k) = C(n-1,k) + C(n-1,k-1) for n > k > 0 C(n,0) = 1, C(n,n) = 1 for n  0 Value of C(n,k) can be computed by filling a table: 0 1 2 . . . k-1 k 0 1 1 1 1 . . . n-1 C(n-1,k-1) C(n-1,k) n C(n,k)

Computing C(n, h): pseudocode and analysis ALGORITHM Binomial(n, k) //Computes C(n, k)by the dynamic programming algorithm ∥nput: a pair of nonnegative integers n≥k≥0 //Output: The value of C(n, k) fori←0 to n do forj←-0 to min(i,k)do if j=for j=i C[i,j←1 else C[i, j]+C[i-1,j-1+C[i-1,jI return CIn, k Time efficiency: o(nk) Space efficiency: o(nk) Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-6 Computing C(n,k): pseudocode and analysis Time efficiency: Θ(nk) Space efficiency: Θ(nk)

Knapsack Problem by DP Given n items of integer weights: Wi W2 values a knapsack of integer capacity W find most valuable subset of the items that fit into the knapsack Consider instance defined by first i items and capacity j(s w Let vi,j be optimal value of such an instance. Then 1=mx1y,+刚120 i-1,∥ ifj<0 Initial conditions: 0j=0 and v,0=0 Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-7

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-7 Knapsack Problem by DP Given n items of integer weights: w1 w2 … wn values: v1 v2 … vn a knapsack of integer capacity W find most valuable subset of the items that fit into the knapsack Consider instance defined by first i items and capacity j (j  W). Let V[i,j] be optimal value of such an instance. Then max {V[i-1,j], vi + V[i-1,j- wi ]} if j- wi  0 V[i,j] = V[i-1,j] if j- wi < 0 Initial conditions: V[0,j] = 0 and V[i,0] = 0 {

Knapsack Problem by DP(example) Example: Knapsack of capacity W=5 item weight value s12 S10 3 2132 S20 s15 capacity/ 012345 0000 v1=1210012 W2=1,V2=10201012222222 Backtracing Wa=3. v2=20 3 0 10 12 22 30 32 finds the actual optimal subset W4=2,v4=1540101525302ie. solution Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-8 Knapsack Problem by DP (example) Example: Knapsack of capacity W = 5 item weight value 1 2 $12 2 1 $10 3 3 $20 4 2 $15 capacity j 0 1 2 3 4 5 0 w1 = 2, v1= 12 1 w2 = 1, v2= 10 2 w3 = 3, v3= 20 3 w4 = 2, v4= 15 4 ? 0 0 0 0 0 12 0 10 12 22 22 22 0 10 12 22 30 32 0 10 15 25 30 37 Backtracing finds the actual optimal subset, i.e. solution

Knapsack Problem by DP(pseudocode Algorithm DPKnapsack(wlLn], vll.n, w ar yo.n,O.w PlL.n, 1.W: int forj: =o to wdo V,j:=0 fori: =0 to n do Running time and space VO:=0 D(nW) fori: =I to n do forj: =I to w do ifwi≤jand+ilwl引>Hz-l,then 阿:叫+i1-iP:jw可 1:=i-l,il;P[:=j return VIn, M and the optimal subset by backtracing Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8

Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-9 Knapsack Problem by DP (pseudocode) Algorithm DPKnapsack(w[1..n], v[1..n], W) var V[0..n,0..W], P[1..n,1..W]: int for j := 0 to W do V[0,j] := 0 for i := 0 to n do V[i,0] := 0 for i := 1 to n do for j := 1 to W do if w[i]  j and v[i] + V[i-1,j-w[i]] > V[i-1,j] then V[i,j] := v[i] + V[i-1,j-w[i]]; P[i,j] := j-w[i] else V[i,j] := V[i-1,j]; P[i,j] := j return V[n,W] and the optimal subset by backtracing Running time and space: O(nW)