Interview: Making change for n cents (arbitrary denominations)

Question

This question occurred as part of an increasingly-difficult problem in an interview. It started ever so simply:

(1) Assuming an infinite supply of coins (in the usual 1, 5, 10, 25 cent denominations). Given n cents, is there always a way to make change for it using the normal denominations?

Yes, since the penny divides all possible values of n cents.

(2) Good, now write a program that accepts n (positive) cents, and returns one possible way of making change for it

Return n pennies.

(3) Smart ass. What if you want to minimize the number of coins required to make the change?

Start with the largest denomination d_i, and take the maximum number of them such that you don't exceed n, m_i. Take n - (d_i)(m_i) and repeat for next largest denomination.

(4) Good, can you prove this solution is optimal?

Yes, { blah, blah }

(5) Ok, *smirk* , now what if, in addition to the n cents, you were given an arbitrary-sized array consisting of arbitrary denominations? You can assume each denomination occurs only once in the array, and that all denominations are positive

My initial thought was just to sort the array of denominations, and apply the same logic as in (4). Luckily, before I communicated this, I caught myself and realized it wouldn't work. But now I realized I was in a pickle.

My next thought was to apply the sum-subset problem to each divisor of n, but realized this was probably overkill. The solution I ended up providing just used the Change-making problem, and short-circuited it when I found some solution. I feel like there has to be a smarter way of doing this though..

The problem reduces to: Given a finite set S of distinct natural numbers, find a linear combination of elements of S that (1) sum to another natural number n, (2) minimize the sum of coefficients in the lin.combination

Answer 1

Actually this problem has been studied as Canonical coin systems, and we even got a paper about how to determine whether a given coin system can support a greedy solution. The original paper may give you some insights: Canonical coin systems for change-making problems.

Alternatively, you can google the key word "Canonical coin systems" for more information.