The <greedy algorithm> repeatedly takes the largest denomination no greater than the remaining postage. For denominations \b[$1,3,4$ and target $6$], it returns $4+1+1$, using three stamps. The optimum is $3+3$, using two. Thus local preference for the largest stamp does not generally solve the <coin change problem> optimally.

Solution

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 7 / d / Solution

 Solution (source code)