COT5405 Analysis of Algorithms
LECTURE 14-15
Dynamic Programming vs Greedy Algorithms
• MatrixChain Multiplication • Activity Selection Problem • Optimal substructure
• Greedy Selection
• Knapsack Problem
Prof. Alper Üngör
COT5405 Analysis of Algorithms 1
Matrix Chain Multiplication
Given a sequence (chain) of n matrices A1, A2,…, An, where Ai is a pi-1×pi matrix
Compute their product A1·A2·…·An using the minimum number of scalar multiplications
Find a parenthesization that minimizes the number of multiplications
COT5405 Analysis of Algorithms 2
Optimal Substructure
Notation. Let Ai,j = Ai·…·Aj for i≤j
• Consider an optimal parenthesization for Ai,j
Say it splits at k, so Ai,j=(Ai·…·Ak)·(Ak+1…·Aj)
• Then, the parenthesization of the prefix Ai·…·Ak
within the optimal parenthesization of Ai,j must be an optimal parenthesization of Ai,k .
COT5405 Analysis of Algorithms 3
Optimal Substructure
Notation. Let Ai,j = Ai·…·Aj for i≤j
• Consider an optimal parenthesization for Ai,j
Say it splits at k, so Ai,j=(Ai·…·Ak)·(Ak+1…·Aj)
• Then, the parenthesization of the prefix Ai·…·Ak
within the optimal parenthesization of Ai,j must be an optimal parenthesization of Ai,k .
(Proof. Suppose it is not optimal, then there exists a better parenthesization for Ai,k . Copy and paste this
parenthesization into the parenthesization for Ai,j . This yields a better parenthesization for Ai,j . Contradiction.)
COT5405 Analysis of Algorithms 4
Dynamic programming
m[i,j] = minimum number of scalar multiplications to compute Aij. We want to compute m[1,n]
Ai,j = (Ai·…·Ak)·(Ak+1…·Aj) pi-1×pk pk × pj
Recurrence for optimal substructure:
• m[i,i] = 0 for i=1,2,…,n
• m[i,j] = mini≤k
A set S of n items with weights wi >0 and
benefits bi> 0 for i = 1,…,n.
S = { (item1, w1, b1 ), (item2, w2, b2 ) ,
. . . , ( itemn, wn, bn ) }
• Find a subset of the items which does not exceed the weight W of the knapsack and maximizes the benefit.
•
COT5405 Analysis of Algorithms 20
0/1 Knapsack Problem
Determine a subset A of { 1, 2, …, n } that satisfies the following:
In 0/1 knapsack a specific item is either selected or not
COT5405 Analysis of Algorithms 21
Variations of the Knapsack problem
• Fractions are allowed. This applies to items such as: – bread, for which taking half a loaf makes sense
– gold dust
• No fractions.
– 0/1 (1 brown pants, 1 green shirt…)
– Allows putting many items of same type in knapsack
• 5 pairs of socks
• 10 gold bricks
– More than one knapsack, etc.
• First 0/1 knapsack problem will be covered then the Fractional knapsack problem.
Greedy vs Dynamic
Brute force!
• Generate all 2n subsets
• Discard all subsets whose sum of the weights exceed
W (not feasible)
• Select the maximum total benefit of the remaining (feasible) subsets
• What is the run time? O(n 2n), Omega(2n)
• Lets try the obvious greedy strategy .
Greedy vs Dynamic
Example with “brute force”
S={(item1 ,5,$70),(item2 ,10,$90),(item3,25,$140)},W=25
• Subsets:
1. {}
2. { ( item1 , 5, $70 ) }
3. { (item2 ,10, $90 ) }
4. { ( item3, 25, $140 ) }
5. { ( item1 , 5, $70 ), (item2 ,10, $90 )}. Profit=$160 **** 6. { (item2 ,10, $90 ), ( item3, 25, $140 ) } exceeds W 7.{(item1 ,5,$70),(item3,25,$140)}exceedsW
8. { ( item1 , 5, $70 ), (item2 ,10, $90 ), ( item3, 25, $140 ) } exceeds W
Profit=$70 Profit=$90 Profit=$140
Greedy vs Dynamic
Greedy 1: Selection criteria: Maximum beneficial item. Counter Example:
S={(item1 ,5,$70),(item2 ,10,$90),(item3,25,$140)} $140
10 lb
5 lb
10 lb
25 lb
W=
25lb
25 lb
$90 $70
5 lb
item1
$140
$70
$90
Optimal =$160 Solution
10 lb
item2
item3
Knapsack
Greedy =$140 Solution
Greedy vs Dynamic
Greedy 2: Selection criteria: Minimum weight item Counter Example:
S={(item1 ,5,$150),(item2 ,10,$60),(item3,20,$140)}
5 lb
20 lb
5 lb
W= 30lb
10 lb
5 lb
$150
5 lb
item1
$60
item2
item3
Knapsack
$60
$150
Greedy =$210 Solution
Optimal Solution
$140
$150 =$290
$140
20 lb
10 lb
Greedy vs Dynamic
Greedy 3: Selection criteria: Maximum weight item Counter Example:
S={(item1 ,5,$150),(item2 ,10,$60),(item3,20,$140)} $60
$140
10 lb
20 lb
5 lb
20 lb
5 lb
W= 30lb
$60 $150
5 lb
item1
$140
$140
$150
20 lb
10 lb
item2
item3
Knapsack
Greedy =$200 Optimal =$290 Solution Solution
Greedy vs Dynamic
Greedy 4: Selection criteria: Maximum benefit per unit item Counter Example
S={(item1 ,5,$50),(item2,20,$140)(item3 ,10,$60),}
W= 30lb
20 lb
10 lb
B/W 1: $10 $50
5 lb
item1
B/W 2: $6 $60
$140 20 lb
$50
Greedy =$190 Solution
B/W: $7 $140
$140
$60 =$200
20 lb
item2
item3
Knapsack
Optimal Solution
10 lb
5 lb
5 lb
Greedy vs Dynamic