Greedy Algorithm

Greedy algorithm is an approach for solving problem by selecting the best option available at the time.

I guess the term “greedy” comes from the fact that I will choose the greedy approach whenever I have been given option to choose.

Example can be explained with the coin problem. Given the amount, what is the minimum number of combination of coins to make the amount?

amount: 710
coins: [10, 100, 200, 500]

Using greedy approach, I take the largest coin possible(500), and the second largest available(200), and so forth until I reach 710.

This will give me 500 + 200 + 10 = 710(3 coins), which yields the solution.

This is fairly intuitive and easy to implement, but it does not always work on this case.

amount: 70
coins: [10, 30, 40, 50]

For the different parameters, we can use greedy algorithm again. I take the largest coin possible(50), and look for second largest available(10). I take another 10 to sum to 70.

This will give me 50 + 10 + 10 = 70(3 coins).

However, we can easily see that 30 + 40 will yield 2 coins, which is the actual answer.

The drawback of greedy algorithm is that it might not work on certain problems, so I, as a developer, need to analyze the problem and figure out if greedy algorithm is the applicable approach for the problem.

The coin problem can be solved with dynamic programming, which I will cover on next story.