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)