Based on the textbook Introduction to Algorithms, the correctness of a greedy algorithm requires a problem to have two properties:
- greedy choice property
- optimal substructure
It is easy to come up with counter examples for which a greedy solution fails due to the lack of the greedy choice property, e.g. the 0/1 knapsack problem. But I find the other possibility pretty hard to imagine. Can anybody give me a problem and a corresponding greedy algorithm which satisfies the first property but not the second?