 Solution

ID: 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

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.

 New to topics? Read the docs here!