# Greedy Algorithms

An algorithm is a method for finding the best solution to a problem. Decisions are made based on the provided solution domain in the greedy algorithm technique. As a greedy person, the closest answer that appears to be the best is picked.

Generally, on the other hand, greedy algorithms do not produce globally optimum solutions.

#### Counting Coins

This task aims to count to a given value with the fewest coins feasible, and the greedy approach forces the algorithm to choose the largest coin available. If we are given coins in the denominations of 1, 2, 5, and 10 and asked to count 18, the greedy technique will be:

• 1 - Choose one of the ten coins; the remaining count is eight.
• 2 - Then, choose one of the five coins; the remaining count is three.
• 3 - Then, select one of the two coins; the remaining count is one.
• 4 -Finally, choosing one of the coins solves the problem.

Though it appears to be working OK, we only need to select four coins for this count. However, if the situation is somewhat different, the same approach may not generate the same optimal answer.

In a monetary system with coins of 1, 7, and 10 values, counting coins for value 18 will be ideal, while counting coins for a count of 15 may require more coins than necessary. The greedy strategy, for example, will consume 10 + 1 + 1 + 1 + 1 + 1 + 1, for a total of 6 coins. The same problem might be solved using only three coins (7 + 7 + 1).

As a result, we can deduce that the greedy strategy selects an immediately optimized solution and may fail in situations when global optimization is a critical priority.

#### Examples

The majority of networking algorithms use the greedy method. Here are a few of them:

• Travelling Salesman Problem
• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Minimal Spanning Tree Algorithm
• Graph - Map Coloring
• Graph - Vertex Cover
• Knapsack Problem
• Job Scheduling Problem

There are many other cases where the greedy technique is used to identify the best answer.