# greedy-algorithm

## Greedy Algorithm

> Approach to solve a problem by selecting the best option currently available

Selects the locally optimal choice at each step , hoping to acheive a global optimum

>

* Simple , easy to implement , fast
* Usually don’t provide globally optimum solution
* Never reconsiders its choices

## Example

Find the maximum sum from root to node

![Actual=27, Greedy=21 , Greedy lost as it picked 7 first
( locally optimum but not globally optimum)](https://3935715743-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FBH37CsSwZp9OqLuOogCr%2Fuploads%2Fgit-blob-432028b94310c67187da84fe0b6cfa71e6606e2a%2FUntitled%202.png?alt=media)

Actual=27, Greedy=21 , Greedy lost as it picked 7 first\
( locally optimum but not globally optimum)

***

## When to use?

2 conditions :

### Greedy Choice Property

> Choosing the best option at each step can lead to a global optimal solution

### Optimal substructure

> An optimal solution to the whole problem contains optimal solution to sub-problems

***
