For denominations \b[$1,3,4$] and target \b[$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.


Solution

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 / Solution

 Solution (source code)