Competitive programming problems are generally divided into a number of categories, each requiring a different skill set, algorithm, or data structure to solve. One subdivision of programming problem topics includes problems which are best solved using what’s known as a “greedy approach”. A greedy algorithm makes locally optimal decisions, which hopefully produce a globally optimal solution. Furthermore, a greedy algorithm does not revisit a previously-made decision. These characteristics make greedy algorithms easy-to-code, straightforward, and efficient / fast. However, coming up with a greedy solution to a problem typically involves more algorithmic thinking; the difficulty in implementing a greedy approach lies in proving that it will work. One commonly-used example is the coin change problem. Suppose you have an infinite supply of coins with values of 1, 5, 10, 25, 50, and 100. Now suppose that you must combine a number of your coins such that the values add up to a certain total, and you must do so with the fewest number of coins possible. How would you solve this problem? The easiest approach is using a greedy algorithm. Let’s say the total you must achieve is 64. A greedy approach would keep a running total, starting at 0. For each iteration, it would determine the highest coin value which would not cause the total to exceed 64 - in this case, 50. Finally, it would add this value to the total, then repeat. In this case, the algorithm would produce the best solution: 50 + 10 + 1 + 1 + 1 + 1 = 64. Let’s look at another coinage system. Suppose you now have an infinite supply of coins with values of 1, 7, 12, and 33, and you again must combine a number of your coins to add up to a certain total with the fewest number of coins possible. Would a greedy approach work in this case? Let’s test it, using the value 36. The algorithm starts off with 0. The highest coin value which would not cause the total to exceed 36 is 33. Adding 33 to 0, it now has a running total of 33. During the next iteration, it discovers that it can only add coins of value 1, since any other value would cause the running total to exceed 36. The solution produced by the greedy algorithm is 33 + 1 + 1 + 1 = 36. The optimal solution is 12 + 12 + 12. Turns out, a greedy approach works only for certain coinage systems (termed “canonical”). For other coinage systems, the solution is a bit more complicated. Like other competitive programming techniques, greedy algorithms are applicable only in certain situations. Still, it’s important to master them, since problems solvable using these approaches are relatively common in competitions. For more information as well as practice problems, visit any of a number of programming websites (GeeksForGeeks, CodeChef, etc.)
0 Comments
## Leave a Reply. |
## Archives
December 2019
## Featured Posts |