# Greedy Algorithms

We have been learning data structures up until now. We have learned how to
organize and store data to support efficient operations like insertion,
deletion, and search, to work appropriately in specific scenarios. Those
operations were, themselves, small algorithms, but are best thought of as
useful steps in a larger scenario.

We now shift to algorithms. An algorithm is a formal, step by step procedure
for solving a computational problem. Algorithms often use data structures as
tools while solving a larger problem.

Most algorithms fall into some established design paradigms. Learning what
works on one problem can give you tools to develop a solution to another
problem on your own.

We'll study the following main categories:

- Brute force: Just trying every possible solution and picking the best one.
- Greedy algorithms: Choosing a choice at each step that seems best for now,
  in hopes of assembling a overall good solution.
- Divide and Conquer: Breaking the problem into smaller, independent
  subproblems.
- Dynamic Programming: Breaking hte problem into smaller but overlapping
  subproblems.

The first is greedy algorithms.

## 1\. Introduction to Greedy Algorithms

A greedy algorithm builds a solution by making a sequence of choices. At each step, it makes the choice that appears best at that moment, without considering future consequences or reconsidering past choices. This approach involves making a "locally optimal" choice in the hope of discovering a "globally optimal" solution.

This method is distinct from other strategies, such as dynamic programming, because it commits to a choice and does not re-examine it.

As with all of the paradigms we'll look at, greedy algorithms are sometimes
appropriate and sometimes not. If a problem is such that a greedy algorithm
results in an optimal solution, then it is said to have the Greedy Choice
Property.

We will examine two examples where this strategy works, and one counter-example where it fails.

  * Activity Selection Problem
  * Fractional Knapsack Problem
  * 0-1 Knapsack Problem (as a counter-example)

## 2\. Activity Selection Problem

**Problem:** Given a set of activities, each with a specific start time and end time, select a subset of non-overlapping activities to maximize the total number of activities performed.

**Incorrect Greedy Strategy:** A naive approach is to select activities based on the earliest start time. This strategy fails. For example, selecting an activity `(0, 6)` (start=0, end=6) might prevent the selection of multiple shorter activities, such as `(1, 2)` and `(3, 4)`.

**Correct Greedy Strategy:** The globally optimal solution is achieved by repeatedly selecting the compatible activity that finishes first.

### Algorithm

1.  Sort the list of activities based on their end times in ascending order.
2.  Select the first activity in the sorted list (the one that finishes earliest). Add it to the results.
3.  Store this activity's end time as `last_finish_time`.
4.  Iterate through the remaining activities.
5.  If the current activity's start time is greater than or equal to `last_finish_time`, it is compatible.
6.  If compatible, add the current activity to the results and update `last_finish_time` to the current activity's end time.

### Implementation (Python)

```python
def MaxActivities(activity_list): # Each activity is a tuple (start, end)
    activity_list.sort(key=lambda x: x[1]) # Sorted by the second element
    chosen = []

    # Loop through from activity that ends first the the one the ends last
    for activity in acts:

        # If the list of chosen activities is empty, or the start time
        # of the activity does not overlap with the ending time of the
        # previously chosen activity, add it to the list
        if len(chosen)==0 or activity[0]>=chosen[-1][1]:
            chosen.append(activity)
    return chosen

# Example from text:
activity_list = [(0,7), (1,4), (7,9), (4,6), (2,5), (3,8)]
# Sorted list becomes: [(1,4), (2,5), (4,6), (0,7), (3,8), (7,9)]
print(MaxActivities(activity_list))
# Output: [(1,4), (5,7), (8,11)]
```

### Runtime Analysis

  * Sorting the $n$ activities by end time requires $O(n \log n)$ time.
  * The selection process involves a single pass through the sorted array, which requires $O(n)$ time.
  * The total runtime is dominated by the sort: **$O(n \log n)$**.

### Proof Intuition (Why This Works)

This strategy works because it satisfies the Greedy Choice Property. By picking the activity that finishes earliest, we maximize the time remaining for subsequent activities, interfering with the fewest potential future choices.

We can prove this with an "exchange argument":

1.  Let $A$ be the activity with the earliest finish time.
2.  Let $O$ be any optimal solution. Let $B$ be the first activity (by finish time) in $O$.
3.  If $A = B$, the optimal solution already includes our greedy choice.
4.  If $A \neq B$, we can "exchange" $B$ for $A$ in the solution. Because $A$ finishes *at or before* $B$ does (by definition), $A$ cannot conflict with any other activities in $O$.
5.  The new solution (with $A$ instead of $B$) is still optimal (it has the same number of activities).
6.  This proves that there is *always* an optimal solution that begins with the greedy choice.

-----

## 3\. Fractional Knapsack Problem

**Problem:** Given a knapsack with a maximum weight capacity $W$ and a set of items, each with a weight and a value, maximize the total value in the knapsack. Items are **divisible**; any fraction of an item can be taken.

**Greedy Strategy:** The optimal solution is achieved by prioritizing items with the highest **value-to-weight ratio** (value per unit of weight).

### Algorithm

1.  Calculate the value-to-weight ratio ($v_i / w_i$) for each item.
2.  Sort the items in descending order based on this ratio.
3.  Initialize total value to 0.
4.  Iterate through the sorted items:
      * If the item's entire weight fits within the remaining capacity ($W$), take the entire item. Add its value to the total.
      * If the item's entire weight does not fit, take the fraction of the item that fills the remaining capacity. Add the corresponding fractional value to the total.
5.  Stop when the knapsack is full.

### Example

Knapsack capacity $W = 7$ kg.

| Item | Weight (kg) | Value | Value-to-Weight Ratio |
| :--- | :--- | :--- | :--- |
| Water | 5.0 | 30 | 6.0 |
| Flour | 2.0 | 10 | 5.0 |
| Sugar | 1.5 | 8 | 5.33 ($8/1.5$) |
| Salt | 0.5 | 4 | 8.0 |
| Ground Pepper | 0.1 | 2 | 20.0 |

### Execution

1.  **Take Pepper** (Ratio 20.0): Take all 0.1 kg.
      * Value: 2.
      * Remaining $W$: $7.0 - 0.1 = 6.9$ kg.
2.  **Take Salt** (Ratio 8.0): Take all 0.5 kg.
      * Total Value: $2 + 4 = 6$.
      * Remaining $W$: $6.9 - 0.5 = 6.4$ kg.
3.  **Take Water** (Ratio 6.0): Take all 5.0 kg.
      * Total Value: $6 + 30 = 36$.
      * Remaining $W$: $6.4 - 5.0 = 1.4$ kg.
4.  **Take Sugar** (Ratio 5.33): We have 1.4 kg of capacity remaining. We take 1.4 kg of the available 1.5 kg.
      * Value added: $1.4 \text{ kg} \times (8 \text{ value} / 1.5 \text{ kg}) \approx 7.47$.
      * Total Value: $36 + 7.47 \approx 43.47$.
      * Remaining $W$: 0 kg.
5.  **Flour** (Ratio 5.0) is ignored, as the knapsack is full.

The maximum achievable utility is **\~43.47**.

### Analysis

- Calculating the value-to-weight ratio for every item is $O(n)$.
- Sorting based on this ratio is $O(n\log(n))$.
- Iterating through the sorted items is $O(n)$.

The total runtime is dominated by the sort, $O(n\log(n))$.

-----

## 4\. The 0-1 Knapsack Problem (A Counter-Example)

**Problem:** A variation of the knapsack problem where items are **discrete** (indivisible). For each item, the choice is binary: 0 (do not take) or 1 (take).

**Greedy Strategy Failure:** The greedy algorithm (using the highest value-to-weight ratio) **does not work** for the 0-1 problem and frequently leads to a non-optimal solution.

### Example

Knapsack capacity $W = 10$.

| Item | Weight ($w_i$) | Value ($v_i$) | Ratio ($v_i/w_i$) |
| :--- | :--- | :--- | :--- |
| Gold Nugget | 7 | 15 | 2.14 |
| Silver Nugget | 5 | 10 | 2.0 |
| Copper Nugget | 4 | 8 | 2.0 |

**Greedy (Non-Optimal) Solution:**

1.  Take **Item 1** (Ratio 2.14). Value = 15.
2.  Remaining $W$: $10 - 7 = 3$.
3.  Cannot take Item 2 (needs 5) or Item 3 (needs 4).
4.  **Final Greedy Value: 15.**

**Optimal Solution:**

1.  Take **Item 2** and **Item 3**.
2.  Total Weight: $5 + 4 = 9$ (which is $\le 10$).
3.  **Final Optimal Value: $10 + 8 = 18$.**

### Why Greedy Fails Here

This example demonstrates that greedy algorithms are not suitable for all problems.

The 0-1 Knapsack problem fails the **Greedy Choice Property**. The locally optimal choice (taking Item 1, the one with the highest ratio) was *not* part of the globally optimal solution. Making that first greedy choice prevents us from ever finding the true optimum.

This problem *does* have optimal substructure, but the greedy choice property does not hold. It must be solved using a different, more exhaustive technique, such as **Dynamic Programming**, which explores multiple possibilities rather than committing to a single greedy choice.

-----

## A key takeaway

While there are problems that can be solved optimally with greedy algorithms,
maybe a more important takeaway is that greedy algorithms are always fast, and
are usually not doing something crazy. For a fast, probably-reasonable
solution (even if it's not optimal), a greedy algorithm is often a good way to
go.