Re: Calculating a given total using only given specific

*To*: mathgroup at smc.vnet.net*Subject*: [mg104305] Re: [mg104294] Calculating a given total using only given specific*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Tue, 27 Oct 2009 04:57:47 -0500 (EST)*References*: <200910260426.XAA18616@smc.vnet.net>

Rick T wrote: > Calculating a given total using only given specific values > > Greetings All > > I'm trying to figure out a way to calculate a given total > using only given specific values. > > Example: > The total given is 46 > The numbers I can use are 56,38,20,12,4, and 1 > so the numbers it should use and come back with would be highest to > lowest > so it should be 38,4,and 4 because > these will add up to 46. Is there a name given to this type of > mathematics? > > And does anyone have an example of how to do this? > > tia sal22 This, or some variant thereof, is called the change making or postage stamp problem. In Mathematica one might use FrobeniusSolve, so named because it is related to finding the Frobenius number of a set of positive integers. Though FrobeniusSolve also works in situations where there is not Frobenius number (see example below). In[1]:= vals = {56, 38, 20, 12, 4}; In[4]:= soln = First[FrobeniusSolve[vals, 46, 1]] Out[4]= {0, 1, 0, 0, 2} In[8]:= Inner[List, soln, vals, List] /. {0, _} :> Sequence[] Out[8]= {{1, 38}, {2, 4}} You did not really pin down how you would handle situations where there might be multiple solutions. For example, had I used 1 in the set, there would indeed be many solutions. Depending on your requirements, the problem might be more specific than the "usual" postage stamp problem. By the way, if the goal is to minimize the number of values used, counting multiplicity, it can be done as below. In[13]:= allvals = Append[vals, 1]; vars = Array[m, Length[allvals]]; In[17]:= Minimize[{Total[vars], Flatten[{Map[# >= 0 &, vars], vars.allvals == 46}]}, vars, Integers] Out[17]= {3, {m[1] -> 0, m[2] -> 1, m[3] -> 0, m[4] -> 0, m[5] -> 2, m[6] -> 0}} So we recover 1*38 + 2*4, for a total of three values used. Daniel Lichtblau Wolfram Research

**References**:**Calculating a given total using only given specific values tia sal22***From:*Rick T <ratulloch@gmail.com>