# What is a Greedy Approach?

In this lesson you will learn what greedy algorithms are and when to use them.

We'll cover the following

## 💰💰 Greedy algorithms

Greedy is an algorithmic paradigm where the solution is built piece by piece. The next piece that offers the most obvious and immediate benefit is chosen. The greedy approach always makes the choice that maximizes the profit and minimizes the cost at any given point. It means that a locally-optimal choice is made in the hope that it leads to a globally optimal solution.

## A real life example

For example:

You just got a new piggy bank to have some savings for your college admission. The bank is small, and can only contain a fixed weight. Therefore, you have to be smart and choose the maximum value vs weight ratio for adding anything into it. You have a fixed number of coins and have to pick them one at a time until the capacity of the bank is reached.

This is also called the Fractional Knapsack Problem. The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to an optimal global solution because we are allowed to take fractions of an item.

💡 How to make the optimal choice?
The greedy algorithm only has one shot to compute the optimal solution. It can never go back and reverse the decision. Hence, the algorithm makes greedy choices at each step to ensure that the objective function is $optimized$.

## Shortest path finding problem

In order to understand the un-optimized solution issue, consider the following shortest path finding problem.

Look at the figure above. You have to travel the minimum distance from the starting point $Venice(S)$ to the ending point $Rome(E)$.

You are given the distance values respective to each path. Your goal is to minimize this (distance) value from $S -> E$

Following the greedy approach, you first pick the minimum choice available at the starting point. So, the path would look like:

$Venice -> Cinque\ Terre\ NP Cost = 10$

Next, we have two options available:

$Cinque\ Terre\ NP -> Rome Cost = 75$

$Cinque\ Terre\ NP -> Florence Cost = 27$

Following the greedy approach, we have to take the path with the least cost , i.e., $27$. Now, we have covered:

$Venice -> Cinque\ Terre\ NP -> Florence$ Cost = 10 + 27 = 37

At Florence, we have only one option to go forward: Naples to Sorrento to Amalfi to Pompeii and finally to Rome.

Hence,

$Venice ->CinqueTerreNP -> Florence -> Naples -> Sorrento -> Amalfi -> Pompeii -> Rome$ $Cost = 10 + 27 + 35 + 2 + 3 + 5 + 17 = 99$

Even though we can easily spot that, instead of taking that first smallest step costing $10$, if we go to $Venice -> Florence$ costing $15$, the whole trip costs $77!$

Let me show you how!

$Venice -> Florence -> Naples -> Sorrento -> Amalfi -> Pompeii -> Rome$ Cost = 15 + 35 + 2 + 3 + 5 + 17 = 77\$

Therefore, it can be concluded that sometimes the greedy algorithm fails to find the globally optimal solution because it does not consider all the data. However, there are many implementations, like Dijkstra’s and Kruskal’s algorithms, of this approach that we will look into further in this chapter.