# Greedy Algorithms

A Greedy Algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate and obvious benefit.

## 1. The Core Concept

At every step, a greedy algorithm makes the **locally optimal choice** in the hope that this choice will lead to a **globally optimal solution**.

*   **Motto:** "Take what looks best right now."

Unlike Dynamic Programming, which solves subproblems and might reconsider previous choices, a Greedy algorithm never looks back. Once a decision is made, it is final.

## 2. Key Properties

For a greedy algorithm to work correctly for a specific problem, the problem must exhibit:

1.  **Greedy Choice Property:** A global optimum can be arrived at by selecting a local optimum.
2.  **Optimal Substructure:** An optimal solution to the problem contains an optimal solution to subproblems.

## 3. Example: The Coin Change Problem

**Problem:** You need to give change for a specific amount (e.g., 36 cents) using the fewest number of coins.
**Available Coins:** Quarter (25), Dime (10), Nickel (5), Penny (1).

**Greedy Approach:**
1.  Pick the largest coin less than or equal to the remaining amount.
2.  Subtract its value.
3.  Repeat until amount is 0.

*   **Step 1:** 36 >= 25. Take one Quarter. Remaining: 11.
*   **Step 2:** 11 >= 10. Take one Dime. Remaining: 1.
*   **Step 3:** 1 >= 1. Take one Penny. Remaining: 0.
*   **Result:** 3 coins (25, 10, 1). This is optimal for US currency.

**Counter-Example:**
If coins were `{1, 3, 4}` and target was `6`:
*   **Greedy:** 4 + 1 + 1 (3 coins).
*   **Optimal:** 3 + 3 (2 coins).
In this case, Greedy fails and Dynamic Programming is needed.

```python
def greedy_coin_change(coins, amount):
    # Coins must be sorted descending
    coins.sort(reverse=True)
    result = []
    
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
            
    return result
```

## 4. Pros and Cons

*   **Pros:** Simple to implement, very fast execution time.
*   **Cons:** Often does not provide the globally optimal solution for complex problems.

[[programming/algorithms]]
[[programming/dynamic-programming]]