Greedy Algorithms A

**greedy**algorithm builds up a solution by choosing the option that looks the best at every step.Say you're a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it?Whenever picking which coin to use, you'd take the highest-value coin you could. A quarter, another quarter, then a dime, a nickel, and finally two pennies. That's a*greedy*algorithm, because you're always*greedily*choosing the coin that covers the biggest portion of the remaining amount.Some other places where a greedy algorithm gets you the best solution:Trying to fit as many overlapping meetings as possible in a conference room? At each step, schedule the meeting that*ends*earliest.Looking for a minimum spanning tree in a graph? At each step, greedily pick the cheapest edge that reaches a new vertex.**Careful: sometimes a greedy algorithm**When filling a duffel bag with cakes of different weights and values…*doesn't*give you an optimal solution: