Greedy Approach: A Deep Dive

💰💰 Greedy algorithms

Greedy is an algorithmic paradigm in which the solution is built piece by piece. The next piece that offers the most obvious and immediate benefit is chosen. The greedy approach will always make the choice that will maximize the profit and minimize the cost at any given point. It means that a locally-optimal choice is made in the hope that it will lead to a globally-optimal solution.

A real life example

Imagine you just got a new piggy bank to save some money for your college admission. The bank is small and can only contain a fixed weight. Each item can only be added once. You’ve got to be smart and choose the maximum value vs weight ratio for putting anything into it.

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 a globally-optimal solution because we are allowed to take fractions of an item.