Greedy Algorithms: 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

Suppose 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 with the maximum value vs. weight ratio. This strategy also leads to a globally optimal solution because we are allowed to take fractions of an item.