Greedy Algorithms

An algorithm is designed to find the best solution to a given problem. The greedy algorithm approach makes decisions based on the given solution domain. As a greedy person, the closest solution that appears to provide the best solution is chosen.

Greedy algorithms seek a locally optimised solution, which may eventually lead to globally optimised solutions. However, greedy algorithms do not always provide globally optimised solutions.

• Counting Coins — The problem is to count to a desired value by selecting the fewest coins possible, and the greedy approach forces the algorithm to select the largest coin possible. If we are given coins numbered 1, 2, 5, and 10 and asked to count 18, the greedy procedure will be followed.

1 − Select one ₹ 10 coin, the remaining count is 8

2 − Then select one ₹ 5 coin, the remaining count is 3

3 − Then select one ₹ 2 coin, the remaining count is 1

4 − And finally, the selection of one ₹ 1 coins solves the problem

Though it appears to be working properly, we only need to select four coins for this count. However, if we slightly alter the problem, the same approach may not produce the same optimal result.

In a currency system with coins of 1, 7, and 10 values, counting coins for value 18 is absolutely optimal, but counting coins for value 15 may use more coins than necessary. The greedy approach, for example, will use 10 + 1 + 1 + 1 + 1, for a total of 6 coins. Alternatively, the same problem could be solved with only three coins (7 + 7 + 1). As a result, we can conclude that the greedy approach selects an immediately optimised solution and may fail where global optimization is important.

• Divide and Conquer – The divide and conquer approach divides the problem at hand into smaller sub-problems, which are then solved independently. If we continue to divide the subproblems into smaller and smaller subproblems, we may eventually reach a point where no further division is possible. The smallest “atomic” sub-problems (fractions) are solved. The solutions to all sub-problems are finally merged to yield the solution to the original problem.

• Divide – This step entails decomposing the problem into smaller sub-problems. Sub-problems should be a subset of the original problem. This step typically employs a recursive approach to divide the problem until no further sub-problems are divisible. Sub-problems become atomic in nature at this point, but they still represent some part of the overall problem.

• Conquer – This step is given a large number of smaller sub-problems to solve. At this level, problems are generally considered solved on their own.
• Merge/ Combine – When the smaller sub-problems are solved, this stage combines them recursively until they form a solution to the original problem. This algorithmic approach works recursively, and the conquer and merge steps are so close together that they appear to be one.