What is Greedy Algorithm?
A greedy algorithm is an algorithm that attempt to find the solution in small steps, making a locally optimal at each step hoping to find a solution that can be applied globally.
Very often Greedy algorithm will give you the most optimal solution, by making the decision that looks the best at the moment. However, this isn’t always the case in the real world.
So let’s start with a problem, given an amount of money, we’ll find the exact bills and coins needed to give back to the person.
Next we create the function with two arguments, currency which is the type of bills and the value of each bill, and amount which is the total amount we are finding change for. We also create an empty hash where the key is the type of the bill, and the value is how much bills we are receiving.
Then we want to loop though each bill (currency) and check if the current leftover money is greater or equals to the current bill value. If it is, increase the bill amount in resultBills and subtract the value from the leftover money.
Greedy Algorithm isn’t always the optimal solution.
For US Money, the greedy algorithm will always give us the most optimized solution. However it might not be the case for a different monetary system.
Lets say that this other currency have a 1 dollar bill, 7 dollar bill, and 10 dollar bill. Using the greedy algorithm to get $15 will result in one 10 dollar bill, and five 1 dollar bill. However, the most optimized solution will be having two 7 dollar bill, and one 1 dollar bill.
The Greedy Algorithm will always give us a solution, but it isn’t necessary the optimal solution.