Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>