In the graph theory section of my Discrete Math course I'll be covering Prim's Algorithm for finding the minimal spanning tree. I'd like to impress upon the students just how special it is that the greedy approach actually works. To do this, it'd be nice to have a variety of easy to understand problems where the greedy algorithm fails to produce the optimal solution.
What are some good examples of problems where the greedy algorithm fails?
The only example I can think of is Egyptian fraction decomposition where taking the next largest unit fraction does not always give the shortest decomposition. But the students don't have much number theory background and I feel like this problem already requires too much introduction. Ideally it'd be nice to have 2 or 3 problems that could be demonstrated quickly in one class period.
(More details: The students in the course have had Calculus and we will have covered Logic, Sets, Recursion, and the basics of Graph Theory by then.)