Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 8 / a

For denominations $1,3,4$ and target $6$, greedy selects $4+1+1$, using three coins. The representation $3+3$ uses two coins and is optimal because there is no denomination six. Hence choosing the largest affordable coin is not generally optimal.