= Solution
In the <coin change problem>, take denominations $\{1,3,4\}$ and target amount $6$. The natural <greedy algorithm> repeatedly chooses the largest denomination not exceeding the remaining amount. It chooses $4$, then $1$, then $1$, for three coins. Yet $3+3=6$ uses only two.
Two is optimal: one coin cannot make $6$ because denomination $6$ is absent, and the displayed pair attains the lower bound. Therefore
$$
\boxed{\text{greedy: }4+1+1\ (3\text{ coins});\qquad
\text{optimal: }3+3\ (2\text{ coins}).}
$$
The locally largest first coin loses the possibility of using the better pair of threes. This supplies a concrete failure of the <greedy-choice property>; <optimal substructure> alone does not justify the greedy choice. The <dynamic programming> recurrence from part (b) would compare all feasible first or last denominations and find the pair.
Back to article page
