Re: sum of coins article in mathematica journal
- To: mathgroup at smc.vnet.net
- Subject: [mg128416] Re: sum of coins article in mathematica journal
- From: Dana DeLouis <dana01 at me.com>
- Date: Sun, 14 Oct 2012 23:39:40 -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
> get the minimum amount of how many coins you need.
Hi. The Generating function for the listing of all solutions is excellent.
However, you may find that at as the sum reaches about 1000, then the timing takes over a minute. Larger numbers would take a very long time to generate all the solutions.
Here's one of many other ideas:
minChange[coins_,tot_]:=Module[
{v,w,obj,c1,c2,sol},
v=Array[w,Length[coins]];
obj = Plus@@v;
c1=Thread[coins.v]==tot;
c2= Thread[v>=0];
sol=Minimize[{obj,c1,c2},v,Integers]//Quiet;
Join[{sol[[1]]},Transpose[{sol[[2,All,-1]],coins}]]
]
coins = {1,5,10,25};
This idea took 0.005 Seconds for a large number:
minChange[coins,123456789] // Timing
{0.005802, {4938276,{4,1},{0,5},{1,10},{4938271,25}}}
minChange[{1,5,10,25,50}, 247]
{9,{2,1},{0,5},{2,10},{1,25},{4,50}}
If interested, the total number of solutions is that given by the generating function for the subset sum problem. See bottom of article:
http://mathworld.wolfram.com/SubsetSumProblem.html
Just an interesting side note:
If your coins are this:
coins={19,23,37,83,89,97};
What we can tell is that there is obviously no solution for sums < 19.
We can quickly tell that there is no solution for a sum of 147.
We know there are solutions for all sums > 147:
FrobeniusNumber[coins]
147
minChange[coins,147]
{\[Infinity],{Indeterminate,19},{Indeterminate,23},{Indeterminate,37},{Indeterminate,83},{Indeterminate,89},{Indeterminate,97}}
minChange[coins,148]
{4,{0,19},{0,23},{4,37},{0,83},{0,89},{0,97}}
= = = = = = = = = =
HTH :>)
Dana DeLouis
Mac & Mathematica 8
= = = = = = = = = =
On Oct 13, 1:08 am, von dremel <peweijn... at gmail.com> 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