Greedy Fundamentals

Opening scenario

You have coins [1, 5, 10, 25] (unlimited supply) and must make change for an amount A using the fewest coins. Your instinct: keep taking the largest coin that fits. It works for A = 30 (25 + 5 = 2 coins). Now the interviewer switches the denominations to [1, 3, 4] and asks for A = 6. Largest-first gives 4 + 1 + 1 = 3 coins — but 3 + 3 = 2 coins is better.

What makes the first coin choice safe in one example but harmful in the other? A strategy needs a reason to work beyond the examples you have tried.

Question progression

Q1 — Largest-first sometimes wins, sometimes loses. What separates the two cases?

Question: The exact same "take the biggest that fits" rule was optimal for [1,5,10,25] and wrong for [1,3,4]. The algorithm didn't change — what property of the problem changed?

Reasoning: "Take the locally best choice…