Greedy Algorithms – Concept and Examples
⏱ Estimated reading time: 2 min
Greedy Algorithms – Concept and Examples
Greedy Algorithms are problem-solving methods that build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit or seems the most promising.
Key Idea
At each step, choose the locally optimal option with the hope that this will lead to a globally optimal solution.
Characteristics of Greedy Algorithms
- Greedy Choice Property: A global optimum can be arrived at by choosing a local optimum.
- Optimal Substructure: The optimal solution can be built from optimal solutions of subproblems.
Examples of Greedy Algorithms
1. Coin Change Problem
Goal: Find the minimum number of coins for a given amount.
coins = [1, 2, 5, 10, 20, 50, 100]
amount = 93
→ Use largest coins first → 50 + 20 + 20 + 2 + 12. Activity Selection Problem
Goal: Select maximum number of activities that don’t overlap.
Greedy Choice: Always pick the next activity with the earliest finish time.
3. Huffman Coding
Goal: Compress data by assigning shorter codes to more frequent characters.
Greedy Choice: Combine the two least frequent nodes first.
4. Fractional Knapsack Problem
Goal: Maximize value in the knapsack when fractions of items are allowed.
Greedy Choice: Pick items with the highest value/weight ratio first.
Advantages
- Simple and efficient for many problems.
- Fast and requires less memory.
Limitations
- Does not always guarantee a globally optimal solution.
- Fails when local choices lead away from the optimal global result.
Common Applications
- Minimum Spanning Tree (Kruskal, Prim)
- Dijkstra’s Shortest Path
- Huffman Coding
- Job Sequencing with Deadlines
Conclusion
Greedy algorithms are ideal when the greedy choice property holds true. They are fast and elegant but must be applied carefully with correctness proofs.
Register Now
Share this Post
← Back to Tutorials