A problem can be solved correctly by a greedy algorithm when it exhibits
Aoptimal substructure AND the greedy-choice property
Bany one of optimal substructure or the greedy-choice property
Cneither property; greedy works on all problems
Dthe dynamic-programming bellman equation
Answer & Solution
Correct answer: A. optimal substructure AND the greedy-choice property
Both properties are required. Optimal substructure says optimal solutions to sub-problems compose into an optimal solution; greedy-choice says the locally best choice is part of some globally optimal solution. Without BOTH, greedy may produce wrong answers (the ₹25/10/1 coin counter-example). Many problems have optimal substructure but not greedy-choice (knapsack, edit distance); those need DP.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for