Greedy Algorithms - Programming for Machine Learning and Business

Making the Best Immediate Choice¶

Greedy choice: fast, local, sometimes final¶

Greedy algorithms repeatedly pick the option that looks best right now. They are often simple and fast — useful in practice — but they only sometimes produce the globally optimal solution. This notebook shows the core idea, a worked counterexample, and lightweight runnable checks you can run in the browser.

Learning goals

Explain the greedy choice rule and when it is a safe strategy.
Run a small coin-change greedy example and compare it to a dynamic programming optimal result.
Practice spotting problems where greedy fails and when to prefer other methods.

def greedy_change(coins, amount):
    used = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            used.append(coin)
    return used

# Example: greedy on canonical coin set
coins = [25, 10, 5, 1]
amount = 41
print('Greedy selection for', amount, '->', greedy_change(coins, amount))

Greedy selection for 41 -> [25, 10, 5, 1]

Core Explanation¶

Greedy algorithms choose the best immediate option at each step. They can be elegant and fast, but they do not guarantee the global optimum in every problem.

def dp_min_coins(coins, amount):
    # Simple DP to compute minimum number of coins (lightweight)
    INF = 10**9
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if a >= c and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] < INF else None

# Counterexample: greedy vs optimal
coins = [4, 3, 1]  # greedy order (largest first)
amount = 6
greedy_sel = greedy_change(coins[:], amount)
greedy_count = len(greedy_sel)
optimal_count = dp_min_coins(sorted(coins), amount)
print('Greedy picks:', greedy_sel, 'count=', greedy_count)
print('Optimal coin count (DP):', optimal_count)

Greedy picks: [4, 1, 1] count= 3
Optimal coin count (DP): 2

Decision Map and Worked Counterexample¶

Worked counterexample (coin change)¶

Consider the coin set [1, 3, 4] and target amount 6. Greedy (take largest coin possible) chooses 4, 1, 1 (3 coins), but the optimal solution is 3, 3 (2 coins). The next code cell computes both to make the difference explicit.

8. Interactive Code¶

9. Guided Practice¶

What is the core idea of a greedy algorithm?¶

Try every possible solution completelyThat describes exhaustive search, not greedy choice.

Make the best local choice at each stepCorrect. Greedy methods choose the locally best option.

Always use recursionRecursion is not required.

Avoid sorting entirelySome greedy algorithms do use sorting.

Which coins are chosen for 41 in the example?¶

[10, 10, 10, 10, 1]That is not what the greedy selection produced here.

[25, 10, 5, 1]Correct. The example repeatedly uses the largest possible coin.

[20, 20, 1]20 is not even in the coin set.

[25, 5, 5, 5, 1]That does not match the greedy process shown.

Exercises¶

Implement a small greedy scheduler: given tasks with start and end times, pick the maximum number of non-overlapping tasks (interval scheduling).
Create a coin set where greedy does produce an optimal result, and explain why for that set greedy works.
Modify the dp_min_coins function to reconstruct an optimal coin list (not just the count) and compare it to the greedy selection for several amounts.

Key Takeaway¶

Greedy methods are powerful when the local choice leads to global structure guarantees (e.g., matroids, certain interval problems). Always test with small counterexamples — if greedy fails, prefer DP or search.