CQH103: Greedy Algorithms – Making the Best Local Choice

What if solving a complex problem was as easy as making the best choice in the moment? That’s the idea behind greedy algorithms.

Greedy algorithms don’t look ahead or reconsider—they make the locally optimal choice at each step and hope it leads to a globally optimal solution.

Sometimes that works beautifully. Sometimes… not so much. Let’s explore how and when greedy algorithms can be your secret weapon.

What is a Greedy Algorithm?

A greedy algorithm builds a solution step by step:

  1. Always choose the best option right now.
  2. Never go back or revise a previous decision.

The hope is that these local decisions add up to the best overall result.

Classic Examples

  • Coin Change (Minimum Coins) – Use the biggest coin possible at each step.
  • Activity Selection – Choose the event that finishes earliest to fit the most.
  • Huffman Coding – Build a tree with the lowest weighted path cost.
  • Kruskal’s / Prim’s Algorithms – Build a minimum spanning tree by adding the cheapest edges.

Greedy vs Dynamic Programming

Feature Greedy Dynamic Programming
Decision basis Current best (local) Global structure & memory
Can revise past decisions? No Yes
Time efficiency Usually faster Often more accurate
When it works When problem has greedy-choice property and optimal substructure  

We covered DP in our last post. Greedy is simpler and faster, but not always correct.

Example: Fractional Knapsack

You have a bag with a weight limit and items with value/weight ratios.

Greedy solution:

  1. Sort items by value/weight ratio.
  2. Take as much of the highest ratio item as possible.
  3. Repeat until full.

This works for fractional knapsack (you can take part of an item).

Python-style Pseudocode

items.sort(key=lambda x: x.value / x.weight, reverse=True)
for item in items:
    if capacity >= item.weight:
        take whole item
    else:
        take fractional part

But it fails for 0/1 knapsack (where you must take the whole item or not at all).

Real-World Greedy Use Cases

  • Scheduling – Like the interval selection problem
  • Network design – Kruskal’s/Prim’s MST algorithms
  • Data compression – Huffman encoding minimizes bits needed
  • Greedy Pathfinding – A* with no heuristic fallback becomes greedy

Challenge Time! 💡

  • Implement a greedy algorithm for the Activity Selection Problem.
  • Compare greedy coin change with the DP version—where do they differ?
  • Try solving the fractional knapsack problem and see how fast it is!

In our next post: Backtracking – how recursion and constraint-solving combine to explore all possibilities, even when greedy fails.