Transcript Greedy, Divide and Conquer

Greedy,
Divide and Conquer
Gary Sham
HKOI 2010
Greedy Algorithm
 Solve the problem by the “BEST” choice.
 To find the global optimal through local
optimal choices, and solve the sub-problem.
Example 1: Coins
 There are 7 kinds of coins:
 $0.1, $0.2, $0.5, $1, $2, $5, $10
 What is the minimum number needed to pay $18 ?
 Use the greatest possible coin every time.
Coins 2
 There are 7 kinds of coins:
 $0.1, $0.2, $0.5, $2, $5, $9, $10
 What is the minimum number needed to pay $18 ?
 Greedy?
 $10 + $5 + $2 + $2
 Actually……
 $9 + $9
Example 2: Fractional Knapsack
 There are N objects, each with weight wi and value
vi. Any amount ( including fractions ) of each item
can be taken provided that the total weight does
not exceed W.
 How much of each item should we take in order to
maximize the total value?
 Consider vi : wi
0-1 Knapsack problem
 Similar to Fractional Knapsack, but you can only
choose to pick the whole item or not.
 Greedy?
Example 3: Activity
 There are n activities, starting at time si and
finishing at fi.
 Choose the maximum number of activities so that
they do not overlap each other.
 Greedy?
Example 4: Diamond Chain
 To find the maximum interval sum.
 When will you choose a negative value?
Example 5: Advertisement
 There are n intervals, [ai, bi]
 Choosing the minimum number of points {pj} so
that each interval contains at least one of the points
Example 6: Egyptian fraction
 An Egyptian fraction is a sum of distinct unit
fraction
 Given a fraction and express it as an Egyptian
fraction
Conclusion
 Hard to prove or disprove.
 Usually easy to code.
 Usually efficient.
 Try to guess.
Divide and Conquer
 Divide
 Break a problem into sub problem(s)
 Conquer
 Solve all sub problem(s)
 Combine
 Solve the problem using the results of the sub
problem(s)
Example 1: Merge Sort, Quick Sort
1~N
1~X
1~Y
1
X+1 ~ N
Y+1 ~ X
2
3
X+1 ~ Z
Z+1 ~ N
N
Example 2: Tower of Hanoi
 Find the minimum number of steps to move N stacks
from Pag0 to Pag2.
 How to move N stacks?
 Move N-1 stacks from Pag0 to Pag1.
 Move the Nth stack to Pag2.
 Move N-1 stacks from Pag1 to Pag2.
 How to move N-1 stacks?
 ……
Example 3: Big Mod
 R = XP mod M
 O(P) is easy: XP = X * XP-1
 0 ≦ P ≦ 231 -1 ……
 X2N = XN * XN
 X2N+1 = X * XN * XN
Example 4: L-pieces
 A 2N * 2N square board with 1 hole.
 How to place L-pieces to cover it?
 What is the sub-problem?
Solution
2N-1 * 2N-1 board with 1 hole
Example 5: Range Maximum Query
 Given N numbers, find the maximum value from ai to
bi.
 O(NQ) ?
 If we know RMQ(3,7), can we find RMQ(3,10) faster?
 RMQ(ai, bi) = MAX( RMQ(ai, ci), RMQ(ci+1, bi) )
 Segment Tree
Conclusion
 Try to divide the original problem to some easier
sub-problems.
 You will see some similar ideas in DP.