Sum of combination

[Michael Wong]

I have a list of numbers in cells A1:A20
I would like to find the combination where the sum of any of these numbers
will equal to the value in cell B1.
Is there a way to do it in Excel? Or in excel VBA?

 

[Michael Wong]

Sorry, just ignore my post, I found it by doing a google search.
Have to do it by vba.

 

[Peo Sjoblom]

Here's a way of doing it

http://tinyurl.com/2g5cq

--
For everyone's benefit keep the discussion in the newsgroup.

Regards,

Peo Sjoblom

 

[Michael Wong]

Yes, that's great.
And what if the solution is not unique?

 

[Peo Sjoblom]

Then solver will select one solution

--


No private emails please, for everyone's
benefit keep the discussion in the newsgroup.

Regards,

Peo Sjoblom

 

[Michael Wong]

Is there possible to get the others solutions also?

 

[Harlan Grove]

Is there possible to get the others solutions also?

...

Possible, yes. Practical, no. First, if your values include both positive and
negative values, it may take Solver a very long time to find the first solution.
If you want to find all sums of subsets of N numbers that equal a given value,
then you'll need to check all 2^N - 1 nontrivial combinations. For N = 20,
that's 1,048,575 different subsets/combinations. If you had 50 values, it'd take
the latest model PCs several months doing nothing else to check all possible
combinations. If you had 100 values, it'd take all current computing resources
en masse a few million years to work out all the combinations.

 

[Michael Wong]

Ummm.... I don't think I can wait this long, will do it by hand, should be
possible to eliminate a subset of the data.

Thanks

 

[Dana DeLouis]

It's a little more involved, but when using Solver, the general idea is to
add the solution back into the constraints. When finding a specific Sum,
and your Binary data (1's) are in, for example, B1,B3, & B5, you add the
constraint that B1+B3+B5<=2. Due to Precision, Tolerance...etc when using
Solver, I will make it <=2.5. Then resolve.
What this is doing is that if one solution used these 3 cells, then any
other solution can not use these same 3 cells. Again, it's a little more
involved, but that's the general idea. It works pretty well, but you have
to set up Solver correctly.

HTH
Dana

 

[Michael Wong]

It's getting more and more interesting now.
Thank you very much for the hint, I'll try to play with it.

 

[Harlan Grove]

It's a little more involved, but when using Solver, the general idea is to
add the solution back into the constraints. When finding a specific Sum,
and your Binary data (1's) are in, for example, B1,B3, & B5, you add the
constraint that B1+B3+B5<=2. Due to Precision, Tolerance...etc when using
Solver, I will make it <=2.5. Then resolve.
What this is doing is that if one solution used these 3 cells, then any
other solution can not use these same 3 cells. Again, it's a little more
involved, but that's the general idea. It works pretty well, but you have
to set up Solver correctly.

...

For an array of 20 values, there are 2^20 - 1 = 1,048,575 nonempty subsets.
Granted it may be possible to use heuristics to eliminate many of these, but
there would still be possibly several thousand subsets to sum. These values may
be summed quickly, but adding constraints to Solver would add considerably to
the total processing time. Also, if there were a few dozen combinations that sum
to the target value, at what point would Solver no longer be able to accomodate
additional constraints? Then back to my previous comment about using Solver when
there are both positive and negative values, you couldn't apply this sort of
constraint. If the set of values were {1,2,3,4,5,6,-1,-3,-5,-7} and the target
value were 10, then 2+3+5 would be a solution, but so would 1+2+3+5-1,
1+2+3+5+6-7, and several others.

If all values were positive, then your proposed constraints would work (subject
to Solver's limitation on the number of constraints it can accept). But if there
were positive and negative values then your proposed constraints would eliminate
possible solutions.

 

[Dana DeLouis]

Yes, working with negative values greatly increases the number of possible
solutions, and is usually best avoided. It all depends on what one is doing
I guess.

For an array of 20 values, there are 2^20 - 1 = 1,048,575 nonempty

subsets.

Just for timing feedback... If I have a column of 20 numbers +1 thru +20,
and have Solver find all the combinations that sum to 20, then Solver found
all 64 unique solutions in 33 seconds on my system.
With the numbers 1-15, Solver found all 27 unique solutions that sum to 15
in 8 seconds.

If one had a 20 cell range from -10 to +9, Solver found about 30
combinations that sum to 10 in a few seconds. However, there are just too
many, and it begins to slow down after it found the 120th solution. I
agree that it's best not to work with models that have negative values.

Dana DeLouis

 

[Michael Wong]

Luckily, I only work positive values. And always less than 10 values.

Thank you very much for the help.

 

[Harlan Grove]

Luckily, I only work positive values. And always less than 10 values.

...

You mentioned A1:A20 in an earlier posting in this thread. Isn't that 20 values?

 

[Michael Wong]

It's just an example...

...
..

You mentioned A1:A20 in an earlier posting in this thread. Isn't that 20 values?