Transcript ppt - HKOI
Greedy TIM AU YEUNG HKOI 2012 Greedy Try some cases Make a guess local optimum -> global optimum Not really a specific algorithm Practice more By feelings Example 1: Coins 7 kinds of coins: $0.1, $0.2, $0.5, $1, $2, $5, $10 Find minimum number of coins needed to pay $n Try n = 3.6 $2, $1, $0.5, $0.1 Try n = 18 $10, $5, $2, $1 Every time use the coin of highest value Example 2: Subarray Sum Given a one-dimensional array of numbers (containing at least one positive number) Find the nonempty contiguous subarray which has the largest sum Calculate maximum subarray ending at each position simple example of DP (will be taught later) If all numbers are non-positive? Example 3: Bridge and Torch Four people come to a river in the night. There is a narrow bridge, but it can only hold two people. Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes, and D in 8 minutes. When two people cross the bridge together, they must move at the slower person's pace. What is the minimum time required for all four people to cross the river? Example 3: Bridge and Torch N people 1) AB Go A Back, YZ Go B Back 2) AZ Go A Back, AY Go A Back N-2 people Example 4: Yogurt factory POJ 2393 C_i: cost to produce one unit of yogurt in week i S: fee to store one unit of unused yogurt per week Y_i: units of yogurt demanded in week i (Yogurt produced in week i and already in storage, can be used to meet yogurt demand for that week) Week i: sell yogurt produced in week j (j<=i) minC = min(C_i, minC + S) Example 5: Persistent Numbers POJ2325 Given a number n, find the smallest number that can reach n by repeatedly multiplying the digits e.g. 679 -> 378 -> 168 -> 48 -> … 48 can be reached from 679 There may be No Solution! Factorize n by 9, 8, 7, 6, 5, 4, 3, 2 in order Distribute them from low-value digit to high-value digit Greedy Practice List POJ 2709 POJ 1042 POJ 1065 POJ 2586 POJ 1328 POJ 1018 HKOJ 1019 HKOJ 1137 HKOJ 2014 If (Greedy_fails) Fail for boundary cases Special solution deal with them Fail for many cases Don’t be greedy Think of other algorithm Greedy Conclusion Guess Try some cases Hard to prove or disprove Easy to code Efficient Practice more!