CS计算机代考程序代写 algorithm chain Dynamic Programming

Dynamic Programming
Chain Matrix Multiplication
2021-02-03 CSC373 Winter 2021 – Sam Toueg 1

Multiplication of 2 matrices
• Multiplying a !×# matrix $ by a #×% matrix & yields a !×% matrix ‘ &
“##
!% × =% #$%
(!” = * +!# , -#”
#%!#%# ⋯ #%$
&
%%”
(
)
!!”
!#” ⋮
!$”

!
! multiplications for each “!” 1≤%≤&
1≤’≤(
• To compute ‘ we need ! · % · # multiplications


2021-02-03 CSC373 Winter 2021 – Sam Toueg
2

Multiplication of 3 matrices
•/=$·&·’
• $·&·’=($·&)·’= $· &·’
• Does the cost of multiplication depend on the multiplication order? Yes!
• Example:
852
2 4×8×5=4
A
0
/
1
Dimension: 4 x 5
Dimension: 8 x 2
ØCostof($·&)·’is: 4,8,5+4,5,2=200 ØCostof$·(&·’)is: 8,5,2+4,8,2=144
• Problem:findthebestordertomultiplyachainofmatrices! 2021-02-03 CSC373 Winter 2021 – Sam Toueg
3

Chain Matrix Product
Ø Input: The dimension 9!’%×9! of every matrix $! in $%, $(, … , $)
Ø Output: Minimum number of multiplications to compute $% · $( · … · $)
• IdeaI—Naïverecursion
• < =, > = Minimum number of multiplications to compute $! · $!*% · … · $”
• Try all the ways to put the outer-level parentheses, and take the best one: ($!·…·$#)·($#*%·…·$”)forall?∈ =,…,>−1
=C==> =C=<>
• Problem
1%)! x 1′ 1′ x 1″ <=,> =B0,
min!+#,” <=,? + +9!’%·9#·9″ ,
• Recursive procedure 2 %, ‘ :
Ø if&=(thenreturn0
Ø elsereturnmin%&'(” , &,. +, .+1,( +1%)! ·1’ ·1″
• Time complexity to compute 2 1, 5 :
2021-02-03 CSC373 Winter 2021 – Sam Toueg
4
6(5)=∑$%#(6 ; +6 5−; +>) !”#

Chain Matrix Product
H(I)=∑)’%(H ? +H I−? +() #$%
•HI =2,∑)’%H?+(I−1),( (1) #$%
• H I + 1 = 2 , ∑) H ? + I , ( (2) #$%
Do “(2) minus (1)′′ ⇒
HI+1 −HI =2,HI +(
⇒HI+1=3,HI+(
=3, 3,H I−1 +( +(
=3(,H I−1 ,+3,(+(
=3)’%,H2 ,+3)'(,(+…+3,(+(
= ( -*’% -‘%
= Θ(3))!
Too many subproblems are computed multiple times!
c
2021-02-03 CSC373 Winter 2021 – Sam Toueg 5

Chain Matrix Product
• Idea II — Dynamic Programming problem size: ‘ − %
• <(=, >) = minimum number of multiplications to compute $! · $!*% · ⋯ · $” <=,> =B0, =C==> min!+#,” <=,? + +9!’%·9#·9″ , =C=<>
• Avoid recomputing the same < =, > subproblems. How?
• By computing them bottom-up: from small > − = size to large size.
For= ←1toIdo<(=,=)←0 @(5)iterations For Z←1toI−1 {*loopbyincreasingproblemsizeZ=>−=*}
For = ← 1 to I − Z
> ← = + Z @ 5′ inner loop iterations
<=,> ←min!+#,”{<=,? + +9!’%·9#·9″}
Return < 1,I Time Complexity: @(5&) 2021-02-03 CSC373 Winter 2021 - Sam Toueg 6 eachmintakes @ 5 J%2K Much better than Θ(3$)! Dynamic Programming 0-1 Knapsack 2021-02-03 CSC373 Winter 2021 - Sam Toueg 1 Overview and Motivation Knapsack Problem • Given:!items,item"hasvalue#! >0andweight&! >0,
weight capacity (
• Assume: (, #!, and &! are integers
• Goal: find a subset ) of items with maximum total value and total weight at most (
• 0-1 Knapsack: We can either take a complete item or not take it 2021-02-03 CSC373 Winter 2021 – Sam Toueg 2

0-1 Knapsack — A Greedy Solution Attempt
• Greedy algorithm:
Ø Sort the items by decreasing value/weight ratio
Ø Take them in that order…
2021-02-03 CSC373 Winter 2021 – Sam Toueg 3

t
0-1 Knapsack
• Greedy algorithm does not work!
• Example: Knapsack with capacity 0 = 4 and items
Items
Weight
Value
Value/ Weight
1
3
10
3+1/3
2
2
6
3
3
2
6
3
• Greedy algorithm: selects item 1 with value 10
• Optimal choice: selects items 2 and 3 with total value 12
2021-02-03 CSC373 Winter 2021 – Sam Toueg 5

Algorithm for 0-1 Knapsack
Let ) be an optimal knapsack for items 1, 2, … , ! and capacity (
There are two possible cases for the last item !:
• !∉).Then)isanoptimalknapsackfor1,2,…,!−1and( (1)
• !∈).Then)=)”∪{!}and)”isanoptimalknapsack
for 1, … , ! − 1 and (′ = ( − &# (2)
Subproblems to solve:
• T(“, U) = value of optimal knapsack for 1, 2, … , ” and capacity U
Bellman Equation: (1)
(2)
max ! #−1,% ,! #−1,%−.! +0! , !(#,%)=( ! #−1,% ,
0,
#1#>0456%≥.! #1#>0456%<.! #1 # = 0 9: % = 0 2021-02-03 CSC373 Winter 2021 - Sam Toueg 6 !(#,%)=( max ! #−1,% ,! #−1,%−.! +0! , ! #−1,% , #1#>0456%≥.!
#1#> 0456%<.! #1 # = 0 9: % = 0 0 (0, *) (1, *) 0 (0, 0) (1, 0) 0, 0 (0, 1) (1, 1) !(0, () = 0 ............... ............... (" − 1, & − '! ) %! 0 0 !(#, 0) = 0 (" − 1, &) 0 (",&) 0 (n, 0) 2021-02-03 (n, 1) ............... CSC373 Winter 2021 - Sam Toueg (n, *) 7 ............... ............... ............... Algorithm for 0-1 Knapsack Knapsack(),, ... , )-, ,,, ... , ,-, -) For 3 = 0 to - do 8(0, 3) ← 0 For9=0to:do8(9,0)← 0 For 9 = 1 to : do running time: Z(! ⋅ () For 3 = 1 to - do if 3 < ). then 8(9, 3) ← 8(9 − 1, 3) else 8(9, 3) ← max{8(9 − 1, 3), 8(9 − 1, 3 − ).)+,.} return 8(:, -) What if we also want to find the optimal set H ← Ø; 9 ← : ; 3 ← - While9 >0and3>0do
of knapsack items instead of just its value?
if 8(9, 3) = 8(9 − 1, 3) then 9 ← 9 − 1
elseH←H ∪{9};9←9−1;3←3−).
return H
2021-02-03 CSC373 Winter 2021 – Sam Toueg 8

Running Time
• Computing all 4 5, 7 :
Ø”∈ 1,…,!
Ø U ∈ {1, … , (} (recall weights and capacity are integers) ØThere are Z ! ⋅ ( distinct T “,U to compute
Ø Each is computed only once
Ø Each takes Z(1) time to compute
Ø So the total running time is Z(! ⋅ () 2″# = 18,446,744,073,709,551,616
• Q: Is this running time polynomial in the input size?
Ø A: No! Because the number ( is exponential in the number of
bits to represent it (e.g., if ( is 64 bits-long, ( could be ≈ 2&’) So computing all T(“, U) is exponential in the size of the input
Ø But this is pseudo-polynomial: polynomial in the input values
Ø Is there a fully polynomial time algorithm? 2021-02-03 CSC373 Winter 2021 – Sam Toueg
iff P=NP!
9

A different algorithm for 0-1 Knapsack
• Q: What if instead of 0, 8;, … , 8< being small integers, we were told that :; , ... , :< and are small integers? Ø Then we can use a different dynamic programming approach! First note that the maximum value that can be achieved with all the ! items (if we had enough knapsack capacity) is: ] = #) + #* + ⋯ + ## 2021-02-03 CSC373 Winter 2021 - Sam Toueg 10 A different algorithm for 0-1 Knapsack • 4(5, 🙂 = minimum capacity needed to pack total value of at least : using items 1, ... , 5 ØGoal:Computemax#∈ 1,...,] ∶T!,# ≤( Ø where ] = #) + #* + ⋯ + ## • Consider item 5 ØIfwedon’tchoose",weneedcapacityT "−1,# Ø I f w e c h o o s e " , w e n e e d c a p a c i t y T ( " − 1 , # − # ) +& &+ !!! ! #,0 = • 1≤-≤. min 0 ∞ ! #−1,0 , .! + ! # − 1, 0 − 0! if 0 ≤ 0 if 0 > 0, # = 0
if0>0,#>0
•0≤%≤/ 2021-02-03
runningtime:0 .⋅/ Sowecanget0(.⋅3)or0(.⋅/) CSC373 Winter 2021 – Sam Toueg 12

Approximate Solution
• Unless P =NP, we cannot hope to solve knapsack exactlyintimeZ cdef !,log(,log] …
Knapsack input size
• But we can find good approximate solutions in poly time:
Ø For any g > 0, we can get a knapsack value
that is at least 1 − g ]∗ , where ]∗ is the optimal value, intimeB C9DE 5,logI,logJ,”#
Ø Such algorithms are approximation algorithms
Ø Core idea for approximate solution to knapsack:
o Approximate all weights and values up to the desired precision o Solve knapsack on approximate input using DP
2021-02-03 CSC373 Winter 2021 – Sam Toueg 13