4.2Greedy algorithms
The idea
A greedy algorithm takes the best-looking choice at every step and never changes its mind. It is correct only when a local best is part of a global best.
Think of it like this: Making change with the biggest coin first: perfect for ordinary coins, a disaster for unusual ones.
Why it exists
GATE asks which problems are greedy-solvable and gives counter-examples.
How it works
- Sort the candidates by a good rule.
- Take the next candidate if it keeps the solution feasible.
- Prove (or check) the greedy-choice property.
- If it fails (0/1 knapsack), use dynamic programming.
Worked example: Activity selection
Sort by finish time and pick every activity that starts after the last chosen one: this maximises the number of activities.
Now play with it
- →Read the table: note the 0/1 knapsack and coin-change failures.
- →Spot which entries are graph algorithms you already know.
| Problem | Greedy gives the optimum? | Rule / counter-example |
|---|---|---|
| Activity selection | yes | sort by earliest finish time |
| Fractional knapsack | yes | take items by value / weight |
| 0/1 knapsack | NO | weights 10, 20, 30, capacity 50, values 60, 100, 120: greedy by ratio takes 60 + 100 = 160, the best is 100 + 120 = 220 |
| Coin change, denominations 1, 5, 10, 25 | yes | canonical coin system |
| Coin change with 1, 3, 4 for amount 6 | NO | greedy 4 + 1 + 1 = 3 coins, best 3 + 3 = 2 coins |
| MST (Kruskal, Prim) | yes | cut property |
| Dijkstra (non-negative) | yes | closest vertex is final |
| Huffman coding | yes | merge the two rarest |
| Job sequencing with deadlines | yes | by profit, latest free slot |
Check yourself
Which problem is NOT solved correctly by the obvious greedy method?
Exam notes (the dense version)
Make the locally best choice and never reconsider. Works when the problem has the greedy-choice property and optimal substructure. Examples: activity selection (sort by finish time), fractional knapsack (by value/weight), Kruskal, Prim, Dijkstra, Huffman coding, job sequencing with deadlines. Greedy fails for 0/1 knapsack and for coin change with unusual denominations.
Previous year questions: Algorithm Design: Divide & Conquer, Greedy, DP (7)
PYQs are grouped by topic, so this is the full set for Algorithm Design: Divide & Conquer, Greedy, DP; try the ones that match this subtopic. Open all 7 on the topic page.