Greedy Algorithms

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)#

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.