Greedy Algorithm in JavaScript
Sharon McCutcheon on Unsplash.
Just want the code? Scroll all the way down for two versions of the code:
- Without comments (just plug and use).
- With comments to have a better understanding of the code.
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.
Greedy Algorithm in JavaScript
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.
We first will need to create the bills in a list of some sort, from the highest to the lowest. For this I’m going to use a JavaScript Object, a hash. We can also use arrays for this but I personally found hash easier to work with. The key is the type of bill, while the value is the amount the bill is worth.
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.
Keep in mind of JavaScript’s float point error, for example when subtracting 6.27 and 5, we result in 1.2699999. To fix this we use toFixed(2), the two is because that in US currency we only use two decimals for our lowest is penny. Feel free to adjust this for any currency that you need.
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.
