Imagine that you bought a book in a bookstore for €69.24, which you paid for with €70 in cash. You are due 76 cents in change, and the cashier now must make a decision whether to give you a fistful of 76 1-cent coins or just six coins ($$20 + 20 + 20 + 20 + 5 + 1 =76$$). Making change in this example is easy, but it casts light on a more general problem: how can a cashier make change using the fewest number of coins?
Different currencies have different possible coin values, or denominations. In Europe the coin denominations are $$(200, 100, 50, 20, 5, 1)$$. In the Roman Republic they were $$(120, 40, 30, 24, 20, 10, 5, 4, 1)$$. The heuristic used by cashiers all over the world to make change (called the greedy approach), iteratively selects the largest coin denominations possible. However, this approach is suboptimal for some denominations!
In this assignment we represent coins from $$d$$ arbitrary denominations as an array of integers $$(c_1, c_2, \ldots, c_d)$$, where the values $$c_i$$ are given in decreasing order. We say that an array of $$d$$ positive integers $$(n_1, n_2, \ldots, n_d)$$ changes an integer $$m$$ if \[ c_1 \cdot n_1 + c_1 \cdot n_1 + \cdots + c_d \cdot n_d = m \] For example, for the Roman denominations $$(120, 40, 30, 24, 20, 10, 5, 4, 1)$$, both $$(0, 1, 0, 0, 0, 0, 0, 1, 0, 3)$$ and $$(0, 0, 0, 2, 2, 0, 0, 0, 0, 0)$$ change $$m = 48$$.
We will consider the problem of finding the minimum number of coins needed to make change, instead of actually producing these coins.
Write a function minimumChange that takes an integer $$m$$ and an array (a list or a tuple) of $$d$$ positive integers. The function must return the minimum number of coins with denominations in the given array that changes $$m$$. If it is not possible to change $$m$$ with coins of the given denominations, the function must return the value -1.
>>> minimumChange(100, [5, 10, 25]) 4 >>> minimumChange(4, (1, 2, 11, 23)) 2 >>> minimumChange(11855, [5, 6, 9]) 1318 >>> minimumChange(2, (3, 5)) -1