Introduction to Greedy Algorithms

Say you are standing at a shop counter. The bill is 70 rupees. You hand over 100. So the shopkeeper has to give you 30 back. What do they do? They reach for the biggest coin or note that still fits. Then the next biggest. And so on. Nobody sits and plans the perfect combination. They just keep grabbing the largest one that works, right now, at each step.

That little habit is the whole idea behind a greedy algorithm. So let us slow down and understand it properly.

🍪 What Is a Greedy Algorithm?

A greedy algorithm is a way of solving a problem by making the choice that looks best at this exact moment. And it never goes back to change that choice.

The thing is, it does not look at the full picture. It does not think about what happens five steps later. It just asks one small question at each step. “Of all the moves I can make right now, which one looks best?” Then it takes that move and moves on.

We call this a local choice. A local choice is the best option you can see at this single step. You do not worry about the steps that come after.

Here is the hope behind greedy. If you keep picking the best local choice every time, maybe all those small best choices add up to the best final answer. Sometimes that hope is true. Sometimes it is not. That is the part you have to be careful about. We will get to it.

💰 The Real-World Analogy: Giving Change

Let us go back to the shopkeeper giving you 30 rupees in change. Suppose the coins available are 20, 10, 5, and 1.

The shopkeeper thinks like this, one step at a time:

• I need to make 30. The biggest coin that fits is 20. Take it. Now 10 is left.
• I need 10 more. The biggest coin that fits is 10. Take it. Now 0 is left.
• Done. I gave a 20 and a 10. That is two coins.

See what happened? At every step the shopkeeper grabbed the largest coin that still fit. They never paused to plan. And for these coins, that simple habit gives the fewest coins possible. That is greedy working beautifully.

🧩 When Does Greedy Actually Work?

Greedy does not work for every problem. It only gives the correct answer when the problem has two special properties. Let me explain both in plain words.

The first one is the greedy-choice property. This means the best local choice at each step really does belong to some best overall answer. In other words, grabbing the biggest coin now never traps you into a worse result later.

The second one is optimal substructure. This means once you make a choice, the smaller problem that is left over is the same kind of problem. After the shopkeeper gives the 20, the leftover task “make 10 in change” is just a smaller version of the original task.

Here is the short version:

• Greedy-choice property — the best move right now is safe. It leads toward the best final answer.
• Optimal substructure — after the move, what remains is a smaller copy of the same problem.

⚠️ When Greedy Fails: A Coin That Breaks It

Now here is the part students must really see. This is where greedy bites you.

Greedy worked for coins of 20, 10, 5, 1. But coins are not always so friendly. Imagine a coin system of 1, 3, and 4. And you need to make 6.

Watch greedy go to work:

• I need 6. The biggest coin that fits is 4. Take it. Now 2 is left.
• I need 2. No 3 fits, no 4 fits, so take a 1. Now 1 is left.
• I need 1. Take a 1. Now 0 is left.
• Greedy used three coins: 4 + 1 + 1.

But wait. Look closer. You could have used 3 + 3. That is only two coins. Greedy gave you three. It lost.

Why did greedy fail here? Because grabbing the 4 looked best at that moment, but it actually trapped you. The greedy-choice property does not hold for the coin set 1, 3, 4. The best local move was not part of the best overall answer.

💻 Greedy Coin Change in Code

Let me show you the greedy coin-change idea in code. We give it a list of coin values from biggest to smallest and a target amount. It keeps taking the biggest coin that fits. Then it counts how many coins it used.

Remember, this code is only correct when the coin set has the greedy-choice property. We run it on the friendly set 20, 10, 5, 1 so the answer comes out right.

#include <stdio.h>

// Take the biggest coin that fits, again and again, until amount is 0
int greedyCoins(int coins[], int n, int amount) {
    int count = 0;
    for (int i = 0; i < n; i++) {        // coins are sorted biggest first
        while (amount >= coins[i]) {     // grab this coin while it still fits
            amount -= coins[i];
            count++;
        }
    }
    return count;
}

int main(void) {
    int coins[] = {20, 10, 5, 1};        // friendly coin set
    int n = 4;
    int amount = 30;
    printf("Coins used: %d\n", greedyCoins(coins, n, amount));
    return 0;
}

Coins used: 2

#include <iostream>
#include <vector>
using namespace std;

// Take the biggest coin that fits, again and again, until amount is 0
int greedyCoins(vector<int> coins, int amount) {
    int count = 0;
    for (int coin : coins) {             // coins are sorted biggest first
        while (amount >= coin) {         // grab this coin while it still fits
            amount -= coin;
            count++;
        }
    }
    return count;
}

int main() {
    vector<int> coins = {20, 10, 5, 1};  // friendly coin set
    int amount = 30;
    cout << "Coins used: " << greedyCoins(coins, amount) << endl;
    return 0;
}

Coins used: 2

public class GreedyCoins {

    // Take the biggest coin that fits, again and again, until amount is 0
    static int greedyCoins(int[] coins, int amount) {
        int count = 0;
        for (int coin : coins) {             // coins are sorted biggest first
            while (amount >= coin) {         // grab this coin while it still fits
                amount -= coin;
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] coins = {20, 10, 5, 1};        // friendly coin set
        int amount = 30;
        System.out.println("Coins used: " + greedyCoins(coins, amount));
    }
}

Coins used: 2

# Take the biggest coin that fits, again and again, until amount is 0
def greedy_coins(coins, amount):
    count = 0
    for coin in coins:               # coins are sorted biggest first
        while amount >= coin:        # grab this coin while it still fits
            amount -= coin
            count += 1
    return count


coins = [20, 10, 5, 1]               # friendly coin set
amount = 30
print("Coins used:", greedy_coins(coins, amount))

Coins used: 2

// Take the biggest coin that fits, again and again, until amount is 0
function greedyCoins(coins, amount) {
  let count = 0;
  for (const coin of coins) {        // coins are sorted biggest first
    while (amount >= coin) {          // grab this coin while it still fits
      amount -= coin;
      count++;
    }
  }
  return count;
}

const coins = [20, 10, 5, 1];        // friendly coin set
const amount = 30;
console.log("Coins used:", greedyCoins(coins, amount));

Coins used: 2

🆚 Greedy vs Brute Force vs Dynamic Programming

Students often mix up these ideas. So here is a quick side-by-side to keep them clear.

So greedy is the fastest of the three. But it pays for that speed with risk. Dynamic programming solves the problem by combining answers to smaller subproblems and storing them. It is slower than greedy, but it is always correct for coin change. When greedy is proven safe, use it. When it is not, reach for dynamic programming.

🙅 Common Mistakes Students Make

Here are the slips that trip people up the most:

• Assuming greedy is correct just because the code runs and gives some answer. A wrong answer is still an answer.
• Picking greedy because it is the easiest to write, without checking the greedy-choice property.
• Forgetting that the same greedy rule can be right for one input and wrong for another, like our two coin sets.
• Mixing up greedy with dynamic programming. Greedy commits and never looks back. Dynamic programming weighs smaller solved pieces.
• Skipping the proof. If you cannot argue why the local choice is safe, you do not really know your answer is right.

🧩 What You’ve Learned

• ✅ A greedy algorithm makes the best local choice at each step and never undoes it.
• ✅ Greedy is correct only when the problem has the greedy-choice property and optimal substructure.
• ✅ Giving change with the largest coins first is greedy, and it works for friendly coin sets.
• ✅ For the coin set 1, 3, 4 making 6, greedy picks 4 + 1 + 1, but 3 + 3 is better, so greedy fails there.
• ✅ Greedy is fast but not always correct, so you must prove it works before trusting it.

🚀 What’s Next?

• Activity Selection Problem
• Fractional Knapsack