Greedy Algorithms:A greedy algorithm always makes the choicethat looks best at the moment.It makes a local optimal choice in the hopethat this choice will lead to a globallyoptimal solution. Greedy algorithms yield optimal solutionsfor many (but not all) problems
Greedy Algorithms: § A greedy algorithm always makes the choice that looks best at the moment. § It makes a local optimal choice in the hope that this choice will lead to a globally optimal solution. § Greedy algorithms yield optimal solutions for many (but not all) problems
CoinChangingSELTCTIONSMEBAELOTGASCEARLESEYEN BMEYLRANANWALLSTREETGreed is qood.Greedis right.Greed worksGreed clarifies,cutsthrough,andcapturesthe essence of the evolutionary spirit.-GordonGecko(MichaelDouglas)
CoinChangingGoal.Given currency denominations:1,5,10,25,100,devisea methodtopayamountto customerusingfewestnumberofcoins.Ex:34dCashier's algorithm.At each iteration,add coin of the largest valuethat does not take us past the amount to be paid.Ex:$2.89
Coin-Changing:Greedy AlgorithmCashier's algorithm. At each iteration, add coin of the largest valuethat does not take us past the amount to be paid.Sort coins denominations by value: Cr < c, <<Cncoins selectedS-while(x0)(let k be largest integer such that Cy xif(k=o)return "no solution found"X←X-CKS←SU(k)1return sQ.Is cashier'salgorithmoptimal?
Greedy works fordenominations 10, 5, and 1Strategy. ,for Proof: (The strategy can be used formany problems. The hard part.)Compare an optimal solution with the solution given bygreedy algorithm (bit by bit, or component bycomponent).Let an optimal solution, denoted (x,Y,z),have:× 10 dollar coins ,y 5 dollar coins and z 1 dollar coins.Let the solution obtained from our greedy algorithmdenoted (x',y', z) have:x'10 dollar coins,y'5dollar coins and z1dollar coins Showthat the two solutionsare the same
Greedy works for denominations 10, 5, and 1 § Strategy for Proof: (The strategy can be used for many problems. The hard part.) § Compare an optimal solution with the solution given by greedy algorithm (bit by bit, or component by component). § Let an optimal solution, denoted (x, y, z), have: x 10 dollar coins , y 5 dollar coins and z 1 dollar coins. § Let the solution obtained from our greedy algorithm, denoted (x’ , y ’ , z ’) have: x’ 10 dollar coins , y ’ 5 dollar coins and z ’ 1 dollar coins. § Show that the two solutions are the same