Interview: Making changes for n cents (custom denominations)

Question

This question arose as part of an increasingly complex issue in the interview. It started so simple:

(1) Assuming an endless supply of coins (in ordinary banknotes 1, 5, 10, 25 cents). Given n cents, is there always a way to make changes for it using normal denominations?

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

(2) Well, now write a program that takes n (positive) cents, and returns one of the possible ways to make a change for it

Return n pennies.

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

Start with the largest name d_i and take the maximum number of them so that you do not exceed n, m_i. Take n - (d_i) (m_i) and repeat for the next highest denomination.

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

Yes, {blah, blah}

(5) Well, * smirk *, now if, apart from n cents, you were given an array of arbitrary size, consisting of arbitrary denominations? You can assume that each denomination occurs only once in the array and that all denominations are positive

My initial thought was to simply sort the array of names and apply the same logic as in (4). Fortunately, before I communicated with this, I caught myself and realized that this would not work. But now I realized that I was in brine.

My next thought was to apply the problem of a subset of the sums to each divisor n, but I realized that this was probably redundant. As a result, I decided to use the change task and was short-circuited when I found some solution. I feel there must be a smarter way to do this, though ...

The task is reduced to:. Given a finite set S of different natural numbers, find a linear combination of elements from S that (1) sums with another natural number n, (2) minimizes the sum of the coefficients in lin.combination

Answer 1

In fact, this problem was studied as Canonical coin systems , and we even got an article on how to determine if a given coin system can support a greedy solution. The original article may give you some ideas: Canonical coins for change problems .

Alternatively, you can use the Google keyword "Canonical coin systems" for more information.

Answer 2

Let d[pos][sum] be the minimum number of coins needed to change money sum , using only the first pos denonyms or infinity, if this is not possible

Let a[i] denote coin i

This can be understood recursively. Rules 1) and 2) will be the basis of recursion.

1) d[any pos][0]=0 (We cannot return money without coins)

2) d[1][each sum] = if (a [1]! = Sum) Infinity else 1 (We can change the amount by one coin only if it has denomination sum )

3) Else:

We can select the current item to make changes or not select it

d[pos][sum]=min(choose,d[pos-1][sum]) where

choose=d[pos-1][sum-a[i]] if sum> = a [i], Infinity otherwise

If we do not select the pos coin number, we will try to do the same with the pos-1 coins. Therefore, d[pos-1][sum]

If we choose the coin number pos, then we only need to make a change for the amount that is less than the current by denominating pos. d[pos-1][sum-a[i]]

But we can choose the coin number pos only if its denunciation is less than or equal to the current amount

---

In real solution

a) Recursion should be replaced by a cycle

or

b) We must save was[pos][sum] - if the value d[pos][sum] has been calculated.

When we try to count d[pos][sum]

if was[pos][sum]==true will just return it. (The value has already been calculated)

else: count it according to steps 1-3 and set was[pos][sum] to true

Answer 3

There is a simple answer that gives you pseudo-polynomial time and space in terms of n (i.e. runtime and memory usage proportional to n instead of the input size, which is log n), and a more complex but more useful answer that can lead you to true polynomial time for fixed items.

Make an array A of size n. This array stores the minimum number of coins needed to create k cents for each k = 1 to n, where A [k] = -1 if it is impossible to make k cents. You can fill this array sequentially from k = 1 to n, writing A [k] = 1 if k is one of your names, and otherwise write A [k] = M + 1, where M is the minimum of A [k - C] for all items C (and A [k] = -1 if all k - C are either not positive or A [k - C] = -1). Then, as soon as you reach n, you can go back through the array starting with n and subtract each value to see which denomination has given you the optimal answer by tracing all the coins used to form the optimal solution.

This is an easy answer. Now the tough answer to a very large n compared to the denominations is revealed when you can make a short cut and just take the largest coin of the denomination for a while, until the total amount of the remaining cents drops below a certain value. I don’t know how to solve this value, but it is possible, and the value always exists, and as soon as you find out, then no matter how big n, all you have to do is calculate how much of the biggest coin to use the first (O (log n) time), and then decide as soon as you fall below the value (constant time if you count fixed notes or runtime depending on the denominations (but not n) if the denominations are not fixed).