Find which numbers sum up to given total

I have been presented with 13 numbers and given a total for the sum of
5 of these numbers. Will excel allow me to find which 5 of the given
numbers add up to my known total.

Sub add_perm()
Dim i As Integer
Dim j As Integer
Dim k As Integer
Dim m As Integer
Dim n As Integer
Dim p As Integer
Dim NN As Integer
Dim SS As Integer

Range("destination").ClearContents
SS = Range("known_total")
NN = Range("numbers") - 1 '13-1

p = 1

For i = 0 To NN
For j = 0 To NN
For k = 0 To NN
For m = 0 To NN
For n = 0 To NN
If Not (i >= j Or i >= k Or i >= m Or i >= n Or _
j >= k Or j >= m Or j >= n Or k >= m Or _
k >= n Or m >= n) _
And (i + j + k + m + n) = SS Then
Range("destination").Cells(p, 1) = i & ", " _
& j & ", " & k & ", " & m & ", " & n
p = p + 1
End If
Next n
Next m
Next k
Next j
Next i
End Sub

Keith Cunningham -

> I have been presented with 13 numbers and given a total for the sum of 5
> of these numbers. Will excel allow me to find which 5 of the given numbers
> add up to my known total. <

You could use Solver.

The setup would be like the standard knapsack problem: thirteen binary
variables as changing cells, each one indicating whether one of the thirteen
numbers is included; a sumproduct of the binary variables times the numbers,
as the target cell; a constraint that the sum of the binary variables equals
five.

- Mike Middleton
www.mikemiddleton.com

If you are looking for a solution (Not necessarily the only one) to a subset
of a group of numbers that will add up to a target number, then this can be
done quite simply with Solver.

Assuming range of numbers in A1:A30, add a set of 0s in B1:B30 and in say
B31 put

=SUMPRODUCT(A1:A30*B1:B30)

Now do Tools / Solver / Set Target Cell 'B31' to 'value of' and put in your
target
number. Then, using the range selector under the 'By Changing cells'
section, select cells B1:B30 as the ones to change and hit enter which will
take you back to the first dialog box. Now hit the 'Add' button, and add
the constraint that B1:B30 must be 'bin' (Means binary as in 1 or 0, and
it's one of the dropdowns, so just hit the arrow and select 'bin') and just
hit Solve. You MUST ensure that in this example, when you add the 'bin'
constraint range, you do not inadvertantly include the formula cell B31,
else you will get an error message such as 'Binary Contsraint cell reference
must include only adjustable cells'

Won't do any more than single solution, but for a Finance Dept that will
often
suffice in this context.

If you are going to look for more than one target number in the data, then
with
that formula in say B31, in B32 type the target number, and in B33 put
=B32-B31.
Now have Solver solve B33 = to 0 with the same constraints. Saves having to
change any values in Solver that way, just type what you want in B32.

Looks quite neat too if you format B1:B30 to a white Font and then use
conditional formatting to highlight values in Col A where Val in Col B = 1

--
Regards
Ken....................... Microsoft MVP - Excel
Sys Spec - Win XP Pro / XL 97/00/02/03

----------------------------------------------------------------------------
It's easier to beg forgiveness than ask permission :-)
----------------------------------------------------------------------------

"Keith Cunningham" <keithcun@utvinternet.com> wrote in message
news:3ao4qaF6b1hshU1@individual.net...
> I have been presented with 13 numbers and given a total for the sum of
> 5 of these numbers. Will excel allow me to find which 5 of the given
> numbers add up to my known total.
>
>

Even though binary is specified in B1:B30, Solver sometimes enters
..999999999999999 instead of 1.
This makes the comparison of B32-B31 to zero fail.
The comparison to 1 in conditional formatting will also fail.
Also, since Keith wants 5 numbers, we have to add a constraint that
the sum of B1:B30 is equal to 5.

Agreed - Nothing is guaranteed but it's always worth a shot. You can always
try using the ROUND function in there to reduce comparison errors, and
that's something I'll always do for checksums and the like.

--
Regards
Ken.......................


"Herbert Seidenberg" <herbds7-msxls@yahoo.com> wrote in message
news:1112126302.324152.63270@f14g2000cwb.googlegroups.com...
> Even though binary is specified in B1:B30, Solver sometimes enters
> .999999999999999 instead of 1.
> This makes the comparison of B32-B31 to zero fail.
> The comparison to 1 in conditional formatting will also fail.
> Also, since Keith wants 5 numbers, we have to add a constraint that
> the sum of B1:B30 is equal to 5.
>

There is a cheap Excel Add-in called SumMatch that solves the problem "http://www.evolucion.com.au/Admin_Pages/SumMatch.aspx"