###### tags: `ADA 7.1` `Greedy Algorithms`
# ADA 7.1: Greedy Algorithms
Textbook Chapter 16 - Greedy Algorithms
Textbook Chapter 16.2 - Elements of the greedy strategy

# What is Greedy Algorithms?

- Always makes the choice that looks best at the moment
- Makes a <span style="background-color:lightyellow">__locally optimal__</span> choice in the hope that this choice will lead to a <span style="background-color:lightyellow">__globally optimal__</span> solution
- __DP__ v.s __Greedy__
| Dynamic Programming | Greedy Algorithms |
| --- | --- |
| has <span style="background-color:lightyellow">__optimal substructure__</span> | has <span style="background-color:lightyellow">__optimal substructure__</span> |
| make an informed choice after getting optimal solutions to subproblems | make a greedy choice before solving the subproblem |
| <span style="background-color:lightyellow">__dependent__</span> or <span style="background-color:lightyellow">__overlapping__</span> subproblems | <span style="background-color:lightyellow">__no overlapping__</span> subproblems |
|||

# Greedy Algorithms
To yield an optimal solution, the problem should exhibit:

1. <span style="background-color:lightyellow">__Optimal Substructure:__</span> an optimal solution to the problem contains within its optimal solutions to subproblems
2. <span style="background-color:lightyellow">__Greedy-Choice Property:__</span> making locally optimal (greedy) choices leads to a globally optimal solution

# Proof of Correctness Skills

1. <span style="background-color:lightyellow">__Optimal Substructure:__</span>

[台大資訊 演算法 | ADA 5.1: Dynamic Programming 動態規劃](https://www.youtube.com/watch?v=x3BCX9hBWZQ&list=PLOAQYZPRn2V6ms1JSww6pqXKf5x0o_gan&index=17&t=26m39s)

2. <span style="background-color:lightyellow">__Greedy-Choice Property:__</span>
- Show that it exists an optimal solution that “contains” the greedy choice using <span style="background-color:lightyellow">__exchange argument__</span>
- For any optimal solution OPT, the greedy choice g has two cases
- g is in OPT: done
- g not in OPT: modify $OPT$ to $OPT'$, $OPT'$ contains g and is at least as good as $OPT$