Changemaking Problem
Making change problems are a variety of partition of an integer problems where the allowed partition sizes may be restricted, i. e., the denominations available and whether the full amount is an available partition size (you can just hand the amount back).
A simple example using common United States coins
You have an unlimited supply of cents, 5cent pieces, dimes (worth 10 cents) and quarter dollars (worth 25 cents).
This problem is kept quite small so that one can verify easily that the answer is correct.
How many combinations, i. e., the order of the coins are not significant, are available to return twentyfive cents?
This is the answer to the question:
\( \left\{\left( \begin{array}{cc} 1 & 25 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 20 \\ 5 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 15 \\ 5 & 2 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 15 \\ 10 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 10 \\ 5 & 3 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 10 \\ 5 & 1 \\ 10 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 5 \\ 5 & 4 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 5 \\ 5 & 2 \\ 10 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 1 & 5 \\ 10 & 2 \\ \end{array} \right),\left( \begin{array}{cc} 5 & 5 \\ \end{array} \right),\left( \begin{array}{cc} 5 & 3 \\ 10 & 1 \\ \end{array} \right),\left( \begin{array}{cc} 5 & 1 \\ 10 & 2 \\ \end{array} \right),\left( \begin{array}{cc} 25 & 1 \\ \end{array} \right)\right\} \)
And our final answer is 13. \( _\square \)
If the full range of permissible partitions is all positive integers less then or equal to amount to be returned, then, the total count would be the partition of an integer \(p(n)\).
Most change making problems encountered here can be done in the available coding environment herein.
For problems which are small enough to fit with the limits of arithmetic and allowed computation, a small recursive program can solve the problem.
In the Rust language:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 
