This may be an accounting or programming question.
I am looking for a computer program/method that will let me find a specific sum
within a series of numbers. For example, if I have 6.25, 10.5, 7.6,
3.4 and 5, I'd like to know which combination adds up to 17.25 (3.4,
7.6 and 6.25). It seems relatively simple and I'm looking for a way to
do this in Excel or Access, but understand that it may be too complex
for these applications. |
Request for Question Clarification by
mathtalk-ga
on
16 Apr 2004 21:05 PDT
How many numbers will you need to be able to handle?
As the series of numbers grows in length, the problem becomes
"combinatorially" more difficult.
Also, does your application require an exact sum, or a sum accurate to
within some error tolerance?
regards, mathtalk-ga
|
Clarification of Question by
amazons_truth-ga
on
17 Apr 2004 07:10 PDT
How many numbers will you need to be able to handle?
On average, less that 20. On rare occasions it can get up to 30.
I'm using this for insurance claims analysis. In general, we have a
bill that is underpaid. I have the amount that's underpaid but need to
single out the individual charges that could add up to the amount. And
yes, in some cases, there is no solution. It does require an exact sum
but the charges that we work with are generally in increments of $.25.
Please let me know if you need any more information.
|
Request for Question Clarification by
mathtalk-ga
on
17 Apr 2004 07:44 PDT
Thanks for the prompt clarification. If more than one solution is
possible, do you have any preference about which one is chosen? Do
you need to know when more than one solution is possible?
Thanks, mathtalk-ga
|
Clarification of Question by
amazons_truth-ga
on
23 Apr 2004 05:32 PDT
I'm sorry for my slow response. It's very rare that more than one
solution would be possible, but, I would need to know in that case.
There is no preference as to which is chosen. I simply need to be able
to see which values were used to come up with the sum.
|
Request for Question Clarification by
mathtalk-ga
on
23 Apr 2004 12:05 PDT
Hi, amazons_truth-ga:
If at least one solution is possible, are you saying it would be
sufficient to provide one solution and a yes/no as to whether other
solutions exist?
regards, mathtalk-ga
|
Clarification of Question by
amazons_truth-ga
on
28 Apr 2004 05:33 PDT
Yes, that would be sufficient.
|
Request for Question Clarification by
mathtalk-ga
on
04 May 2004 09:01 PDT
Hi, amazons_truth-ga:
I've written a short Prolog program to solve these kinds of problems.
Perhas you could post the values for a "real world" example, e.g. lots
of candidate cost items, so I can test how well it performs?
regards, mathtalk-ga
|
Clarification of Question by
amazons_truth-ga
on
05 May 2004 05:27 PDT
Here you are. I would be looking for what added up to $2262.50. I've
included the values with and without labels.
562.00
174.50
200.00
84.75
288.25
1,568.50
3,732.50
2,539.00
140.50
6,735.00
2,425.00
1,620.00
453.75
468.00
Revenue Labels
ROOM CHARGES 562.00
PHARMACY 174.50
DRUGS/IV SOLUT 200.00
DRUGS/SELF ADMIN 84.75
PHARMACY/OTHER 288.25
IMPLANTS 1,568.50
MED-SUR SUPPLIES 3,732.50
LABORATORY 2,539.00
XRAY/DIAGNOSTIC 140.50
OPERATING ROOM 6,735.00
ANESTHESIA 2,425.00
RECOVERY ROOM 1,620.00
TREATMENT RM 453.75
OBSERVATION RM 468.00
|
Request for Question Clarification by
mathtalk-ga
on
07 May 2004 18:40 PDT
Hi, amazons_truth-ga:
My short program quickly found this solution (amounts are converted to
whole cents, to make the arithmetic exact) and also determined that
there were no additional solutions:
Lo = [17450, 46800, 162000] ;
no
These items' labels are respectively the Pharmacy, the Observation
Room, and the Recovery Room.
Assuming this to be a fairly typical problem, I think the speed will
be satisfactory (it returned in the blink of an eye, running as
interpreted code).
However as it is written in Prolog, and you are intending this for
commercial application, I will raise the issue of how much your budget
will allow to have this integrated with Excel or Access. To write an
equivalent program in C or Visual Basic will run to dozens of lines;
the Prolog program is essentially four clauses for one predicate
though some additional code would be needed to interface with a VBA
environment like Excel/Access. I intended it to run against input data
in sorted order, but in my experimentation it seemed to work even
without that preparation.
The list price offered for the Question suggests a rather limited
budget, so I thought it best to explore the issue before proposing a
solution that does not meet your requirements.
regards, mathtalk-ga
|
This sounds very similar to the knapsack problem
(http://www.nist.gov/dads/HTML/knapsackProblem.html), although there
are a few differences, such as that the weights are the same as the
values, and you're looking for an exact sum, not for just the maximal
value. My point, however, is that at first glance this seems to be a
complex algorithmic quandary, and the easiest way to go about it might
just be to do it by brute force. For example, something like the
following might work:
findsum(sum,list[])
If list is empty, then return true if sum=0, else return false.
If findsum(sum,list[1..end]) then return true.
If findsum(sum-list[0],list[1..end]) then return true.
Otherwise, return false.
end findsum
This particular algorithm would most likely take approximately forever
for a large dataset, but it would be manageable for something small.
There may be ways to speed it up.
At any rate, I doubt that something like this is already coded into
Excel or Access, and you may have to end up writing the code yourself. |
