The special money-changing problem is only one of the many variations of the classical money-changing problem, which is also only one of the many variations of the widest optimisation problem in this story – the knapsack problem. The narrowest of these variations, the special money-changing problem, asks for what denominations of money $a_1, a_2, \ldots , a_t$, is there exactly one way to make change, using the fewest number of coins possible, for every amount for which change can be made using only coins of these denominations. We will provide a solution to this problem in the case with coins of two different denominations and a few methods for finding (or testing the correctness of) solutions in the case with coins of three different denominations, which all meet certain conditions.
|