GD said:
I have a challenge for all you Sir Accessalots out there!
Let's say I have a list of 30 numbers. I also have another number, larger
than the rest. What I need is something that will:
(My first preference) provide me with all possible combinations of numbers
in the list of 30 that add up to the larger number;
(My second preference) provide me with at least one combination of numbers
in the list of 30 that add up to the larger number;
Or (my third preference) tell me that at least one combination exists.
Can Access (or any other app you know of) do this?
Here are some thoughts toward a possible VBA solution:
A brute force method could involve counting in binary from 1 to 2 ^ 30 -
1 and adding the kth number when the corresponding bit is 1, then
checking the sum against the given number -- a tad gauche.
This problem is related to:
Weisstein, Eric W. "Greedy Algorithm." From MathWorld--A Wolfram Web
Resource.
http://mathworld.wolfram.com/GreedyAlgorithm.html
Search the same site under "Partition" to show that the Mathematica
program has some functions for partitioning.
A restatement of the problem:
Find the number of partitions of N where each partition is exactly one
of the positive integers A1, A2, ..., Ak where k = 30.
Note that the Ai values are not necessarily distinct and that for a
well-posed problem, each Ai should be < N.
When binary bits are used in a loop, every possibility is checked. Once
your sum gets above N no more terms should get attempted so potentially
many less combinations, depending on the particular data, need to be
evaluated.
Plan: Get strings of 0's and 1's indicating which Ai's are used in the sum.
A(Val(Mid(strAnswerBits, I, 1)) * I) can be used to generate an answer
string from strAnswerBits. Something like (air code):
Const LISTMAX = 30
....
If Mid(strAnswerBits, I, 1) <> "0" Then
strAnswer = strAnswer & A(Val(Mid(strAnswerBits, I, 1)) * I)
If I <> LISTMAX Then
strAnswer = strAnswer & " + "
End If
End If
"1001000...1" => A1 + A4 + ... + A30
There might be several answer strings or one or none that satisfy the
condition.
Suppose your substring is '101'. Let the Residue for that substring be
N - A1 - A3. That is, the amount left over after those choices. (Did
someone mention the possibility of a recursive solution?)
Maybe look at traversing a binary tree where left branches indicate a 0
value and right branches indicate a 1 value for each Ai. All the nodes
along a given tier correspond to the same Ai. Once the Residue is zero
or less, there's no need to visit any sibling nodes of that node. If
the Residue is zero, then the string is padded with 0's as necessary and
a solution has been found. If the residue is less than zero you've
reached a cul-de-sac and no solution will be forthcoming through that
node. Alternatively, when a candidate substring doesn't pan out, you
can calculate how many numbers start with that substring and skip them
in the binary loop. Although much computation can usually be skipped,
there is no guarantee that the data will not be so pernicious that you
have to check every node. I hope the following displays the way I'd like:
"101" =>
x A1
\
\
x x A2
/
/
x x x x A3
\
\
x x x x x x x x
A SQL solution might start with the ideas from the following thread:
http://groups.google.com/group/microsoft.public.access/browse_frm/thread/228ad5285b0ebbd2
The Christmas combinatorics problem is also related but it's a bit
abstract
:
http://groups.google.com/group/comp.databases.ms-access/msg/905de7b0e1696857
The disclaimer goes double for this problem
.
James A. Fortune
[email protected]