Greedy Algorithm

In this tutorial, you will learn what a Greedy Algorithm is. Additionally, you will discover an illustration of a greedy approach.

What is a Greedy Algorithm?

In the Greedy Algorithm, a set of resources are recursively divided dependent on the maximum, prompt accessibility of that resource at some random phase of execution.

A greedy algorithm is a methodology for tackling an issue by choosing the best choice accessible right now, without stressing over the future outcome it would bring. As such, the locally best decisions target delivering worldwide best outcomes.

This algorithm may not be the best choice for every one of the issues. It might create wrong outcomes now and again.

This algorithm never returns to turn around the choice made. This algorithm works in a top-down approach.

The fundamental benefit of this algorithm is:

1. The algorithm is easier to describe.
2. This algorithm can perform better compared to the different algorithm (in any case, not altogether cases).

---

Feasible Solution

A feasible solution is the one that gives the optimal solution for the issue.

---

Greedy Algorithm

1. To begin with, the solution set (containing answers) is vacant.
2. At each progression, an item is added to the solution set.
3. In the event that the solution set is possible, the current item is kept.
4. Else, the item is rejected and never rethought.

---

Example – Greedy Approach

Problem: You have to make a change of an amount using the smallest possible number of coins.
Amount: $28

Available coins:
  $5 coin
  $2 coin
  $1 coin

Solution:

1. Create an empty solution-set = { }.
2. coins = {5, 2, 1}
3. sum = 0
4. While sum ≠ 28, do the following.
5. Select a coin C from coins such that sum + C < 28.
6. If C + sum > 28, return no solution.
7. Else, sum = sum + C.
8. Add C to solution-set.

Up to the initial 5 iterations, the solution set contains 5 $5 coins. From that point forward, we get 1 $2 coin lastly, 1 $1 coin.

---

Greedy Algorithm Applications

Selection Sort

Knapsack Problem

Minimum Spanning Tree

Single-Source Shortest Path Problem

Job Scheduling Problem

---

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.

Greedy Algorithms