Excel: How to determine which elements sum to a total

[NCNY]

Hello:

I have an array of numbers, such as:

7.43
35.04
35.10
14.99
46.98
8.55
26.97
132.07
29.72
114.29
2.59
109.40
75.00
2.85

I'd like to have Excel figure out which of these numbers would sum to a specific total, such as 132.50, or whether the solution is impossible with this set.

I've come upon some postings on "VBA code to find multiple matching combinations", but they don't seem to work right for this particular problem. This seems like a "lots of for-loops" type of problem to me, but perhaps anyone already has a code snippet that would do what I like, and wouldn't mind sharing?

Thank you!

 

[Gavona]

Do you need a precisely exact match?
How many numbers in your real data?

I tried the random approach (so someone must have a more mathematical solution!)

Copy the numbers into a workbook starting in cell B2
Column A uses the formula =rand()(copied down)
Named range for these two columns of data = myArray

Further column uses formula =SUM($B$2:B2) copied down
this range names mySums (basically a running total)

Single cell named ranges with formulae as follows:
myTarget = [the target value eg 132.5]
myMatch: =MATCH(myTarget,mySums,0)
myResult: =ISERROR(myMatch)


Basically re-calculate the worksheet. (this creates new set of random numbers)
Sort the myArea range

Repeat until myResult=False
at this point one of the running totals (in mySum) equals the target. MyMatch tells you which one.

Sub Macro1()
Do While Range("myResult").Value = True
range("mySums").Calculate
range("myArray").Calculate

Range("myArray").Sort Key1:=Range("A2"), Order1:=xlAscending, Header:=xlGuess, _
        OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, _
        DataOption1:=xlSortNormal
Loop
End Sub

Probably won't work with real data volumes and you have to break out of the macro if no match is found - but you could always do something about that! Of course turn off screen updating, set calculation to manual.
IF it works then I would be interested to hear how performance compares with a more elegant solution! Awful I would think but it does rely on 'native' excel functionality using efficient code (the inbuilt bit not mine!)


Gavin

 

[SkipVought]

NCNY (Programmer)

As a fellow programmer, I surmize that you've surely worked on some logic or an algorythm as a starting point. Maybe even some code.

You might post these ideas or code, so we can see what you have done so far.

Skip,

_{Just traded in my old subtlety...
for a NUANCE!}

 

[Gavona]

If there is more than one solution do you need to identify them all?
If a number appears more than once in your array and features in a solution do you need to differentiate as two solutions?

Would either of these help?

http://www.digdb.com/excel_add_ins/mix_match_sets_all_combinations/

http://www.beyondtechnology.com/tools_combinator.shtml

You could start by looking to list (or rather sum) all possible "combinations" of numbers from your array. There are potentially a huge number of these.
To make the programme more efficient you may be able to eliminate some combinations....

I am NOT a programmer so I will stick to suggesting pseudo code:

mySum=0
Generate myArray1 to contain a list of unique values in the array, sorted ascending
for each UniqueValue1 in myArray1
  mySum=mySum+Unique value
  If mySum = myTarget then solution found
  if mySum > myTarget then End Next
  Generate myArray2 to contain a unique list of all remaining unique values, sorted ascending

  For each UniqueValue2 in myArray2
     mySum=mySum+UniqueValue2 (UniqueValue1+UniqueValue2+..)
     If mySum = myTarget then solution found 
     if mySum > myTarget then End Next
     Generate myArray3 to contain a unique list of all remaining unique values, sorted ascending

Note that to allow for values appearing more than once in the original data myArrayn must be based on the original data excluding just one instance of UniqueValue1, one instance of UniqueValue2,....., one instance of UniqueValuen-1


Gavin

 

[macropod]

Hi folks,

We went through almost exactly the same thing back in July. See:

http://www.tek-tips.com/viewthread.cfm?qid=1485698

Cheers

[MS MVP - Word]

 

[fredericofonseca]

yep. my post that one. not easy as mentioned on it.

Regards

Frederico Fonseca
SysSoft Integrated Ltd

http://www.syssoft-int.com

FAQ219-2884
FAQ181-2886

 

[NCNY]

macropod,

Thanks!! I think I can adapt the code to search for all possible combinations.

It occurred to me that the problem amounts to essentially generating all possible samples without replacement from a population of n values. A statistical package, such as SAS, might be more suited for a less-CPU intensive solution.

 

[macropod]

Hi NCNY,

I think I can adapt the code to search for all possible combinations.

If you do, be prepared to wait a loooooooooooooooooooong time for the macro to do its thing.

Cheers

[MS MVP - Word]