       Re: sum of coins article in mathematica journal

• To: mathgroup at smc.vnet.net
• Subject: [mg128422] Re: sum of coins article in mathematica journal
• From: Bob Hanlon <hanlonr357 at gmail.com>
• Date: Sun, 14 Oct 2012 23:41:41 -0400 (EDT)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com
• Delivered-to: l-mathgroup@wolfram.com
• Delivered-to: mathgroup-newout@smc.vnet.net
• Delivered-to: mathgroup-newsend@smc.vnet.net
• References: <k5assc\$noo\$1@smc.vnet.net>

```You can just use Minimize and it will also give you the total number of coins

minimalChange[coins_, amount_] := Module[
{var = r /@ Range[Length[coins]]},
Minimize[{Total[var],
coins.var == amount,
var, Integers] /.
{(r[n_] -> 0) :> Sequence[],
(r[n_] -> m_) :> {coins[[n]], m}}]

coins = {1, 5, 10, 25, 50};

minimalChange[coins, 247]

{9, {{1, 2}, {10, 2}, {25, 1}, {50, 4}}}

minimalChange[{4, 7, 11, 23}, 247]

{13, {{7, 1}, {11, 3}, {23, 9}}}

minimalChange[{5, 7, 11, 26}, 377]

{18, {{7, 4}, {11, 1}, {26, 13}}}

Bob Hanlon

On Sun, Oct 14, 2012 at 12:15 AM,  <daniel.lichtblau0 at gmail.com> wrote:
> On Saturday, October 13, 2012 12:08:01 AM UTC-5, von dremel wrote:
>> a long time ago I read a short text in mathematica journal.
>>
>> A neat little program that calculated the numer of coins needed to reach a certain sum. you put in the coin values e.g. 25 cent 50 cent etc and got the minimum anount of how many coins you need.
>>
>> I think Allan Hayes wrote it.
>>
>> does anyone have a pointer to it please?
>>
>>
>> Peter W
>
> You might try looking in library.wolfram.com. I believe (some? many?) back issues of TMJ are archived there.
>
> If I'm not mistaken, the method involves looking at a coefficient of 1/((1-x*t)*(1-x^t^5)*(1-x*t^10)*(1-x*t^25)*(1-x*t^50)) expanded at the origin. Specifically, to make j cents in total change, look at the jth coefficient. Find the summand that uses smallest total powers of x[k]s.
>
> Here is a bit of code for this.
>
> minimalChange[coins_, amount_] := Module[
>   {len = Length[coins], mu, mus, x, ratfun, coeff, totals, bestpos},
>   mus = Map[mu, coins];
>   ratfun = Times @@ (1/Table[1 - mus[[j]]*x^coins[[j]], {j, len}]);
>   coeff = (List @@
>      Expand[SeriesCoefficient[ratfun, {x, 0, amount}]]);
>   coeff = coeff /. Times -> Plus;
>   totals = Map[# /. mu[_]^j_. :> j &, coeff];
>   bestpos = Ordering[totals, 1];
>   coeff[[bestpos]] /. Plus -> List /. mu[k_]^j_. :> {k, j}
>   ]
>
> Example:
>
> coins = {1, 5, 10, 25, 50};
>
> In:= minimalChange[coins, 247]
>
> Out= {{{1, 2}, {10, 2}, {25, 1}, {50, 4}}}
>
> So 4 50 cent pieces, 1 quarter, 2 dimes, two pennies. No surprises here.
>
> I think this is a bit slow. There may be a more efficient way to get at the relevant series term.
>
> I should allso note that the "obvious" greedy method does not work on all possible coin sets.
>
> In:= minimalChange[{4, 7, 11, 23}, 247]
>
> Out= {{{7, 1}, {11, 3}, {23, 9}}}
>
> Also one can have a tie.
>
> In:= minimalChange[{5, 7, 11, 26}, 377]
>
> Out= {{{7, 4}, {11, 1}, {26, 13}}}
>