[Math] On problems of coins totaling to a given amount

algorithmscombinatoricsinteger-partitionsoptimization

I don't know the proper terms to type into Google, so please pardon me for asking here first.

While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so coins of a currency (let us, say, use the coins of the American dollar as an example) can be used to total to a given amount. For instance, one can have five coins totaling to forty cents: three dimes and two nickels.

1) How does one find other $n$ combinations of coins that can total to a set amount?

To use my example, are there other five coins that can total to forty cents? How might one algorithmically prove that those are the only solutions?

2) Given an amount not equal to a denomination, what is the minimum number of coins needed to be equivalent to the given amount?

For instance, one can have forty cents in three coins: a quarter, a dime, and a nickel. How does one algorithmically show that the "magic number" for forty cents is three (i.e., one cannot find two coins whose amounts total to forty cents)?

As mentioned already, this isn't homework; just idle curiosity. Any pointers to algorithms would be appreciated!

Best Answer

Question (2) is a known problem; it's called the change-making problem. The Wikipedia page lists integer programming and dynamic programming as solution approaches. The change-making problem is also a variation of the famous knapsack problem. One of the implications of that is that since the standard version of the knapsack problem is NP-complete, it's likely that the change-making problem is as well, dashing hopes for an easy-to-find fast algorithm for solving it.

However, the Wikipedia page also says that for the US and most other coin systems, the greedy algorithm will give the optimal solution. Thus for the nickel/dime/quarter example you give, the optimal solution is to use as many quarters as you can, then account for what's left by using as many dimes as you can, then make up the rest with nickels. So 3 is the minimum number of nickels, dimes, and quarters required to make 40 cents.

Here's the integer program formulation for Question (2). If you let $x_i$ be the number of coins of type $i$ to be used, $d_i$ be the denomination of coin type $i$, and $A$ be the target amount, Question (2) entails solving

$$\min \sum_i x_i $$ subject to $$\sum_i d_i x_i = A,$$ $$x_i \geq 0, x_i \in \mathbb{Z}.$$

While integer programs are hard to solve in general, for small problems like the example you give a good IP solver will return a solution very quickly. For instance, if you take coins of denominations 31, 37, and 41 cents (since nickels, dimes, and quarters are too easy :) ), and want to know the minimum number required to be equivalent to 2011 cents, the solver Lingo requires only the following code to find the answer:

MIN = x1 + x2 + x3;
31*x1 + 37*x2 + 41*x3 = 2011;
@GIN(x1); @GIN(x2); @GIN(x3);

Lingo outputs the optimal solution as $x_1 = 0, x_2 = 20, x_3 = 31,$ with only 7 solver iterations and "00:00:00" time elapsed. So the minimum number of coins is $51$.

You did ask specifically for an algorithm. Many IP solvers (including Lingo) use the branch and bound algorithm, which has solving a linear program (usually with the simplex method) embedded in it.

For Question (1), you could use the following integer program to find a single solution or determine that one does not exist. (In the latter case, the IP solver will report that the problem is infeasible.)

$$\max 1$$ subject to $$\sum_i d_i x_i = A,$$ $$\sum_i x_i = n,$$ $$x_i \geq 0, x_i \in \mathbb{Z}.$$

Again, for small problems a good IP solver will return a solution almost instantaneously. I'm not sure how (or even if it's possible) to modify an IP approach to find all solutions like you request. The generating function techniques mentioned by cardinal and in the question linked to by Derek Jennings will tell you how many solutions there are, but I'm not sure if they will tell you exactly what those solutions are.

Related Question