Finding all combinations that reach a target

  • Thread starter Thread starter joel
  • Start date Start date
J

joel

Hi all,
I tried a clever way to solve my problem but I couldn't...
Here my problem
I have 3 types of populations with different weights
col A = 4, col B = 2, col C = 1
So one A is equal to 2B or is equal to 4C
So one B is equal to 2C or is equal to 1/2 A
I would like to compute all possible ABC combinations to
reach a target (40 for example)
Example: 10A = 40 but also 5A + 10B or 40C . . .
How can I build a table showing all possible combinations ?
Do somebody has a bright subtle idea ?
Thanks in advance !!!
Joël
 
[Converting all @#$%^&* HTML char encodings back to nice clean ASCII.]

Here my problem
I have 3 types of populations with different weights
col A = 4, col B = 2, col C = 1
So one A is equal to 2B or is equal to 4C
So one B is equal to 2C or is equal to 1/2 A
I would like to compute all possible ABC combinations to
reach a target (40 for example)
Example: 10A = 40 but also 5A + 10B or 40C . . .
Click to expand...

So 'combinations' could mean just one entry from one of the columns? Would
combinations be limited to just one entry from each column? If so, there'd be
7*N_A*N_B*N_C combinations to check, where N_A, N)B and N_C are the number of
entries in columns A, B and C, respectively. If each column contained 20
entries, this'd be 56,000 different combinations to check. If combinations could
include any number of entries from each column, that's 2^(N_A+N_B+N_C)-1
possible combinations to check. Again, if all three columns had 20 entries each,
that's 1.153E18, which would take roughly 7 years(!) to calculate on a machine
capable of processing 5 *billion* combinations per second. There are heuristics
that could be used to reduce this to just a few weeks.

There are techniques involving Solver that could be used to find a *single*
answer, often quickly but possibly requiring a LONG time. Finding all
combinations would unavoidably take a while.
 
Joel,

If you restrict yourself to integer values - which you seem to imply - (or decimal values that are relatively widely spaced) for
columns A, B, and C, then the problem is both simple and quickly solved. On my machine, the macro finished too quickly to tell that
it was running. There are only 122 integer solutions.

In your example, A can only vary from 0 to 10, B from 0 to 20, and C from 0 to 40. But there are other constraints: if A is 9, then
B can only be 0, 1, or 2, etc.

Anyway, the code below solves for any number, given any 3 weights (set as variables), and given any step size - smaller steps mean
more solutions. Of course, as the number gets bigger and the step size smaller, then the solution set gets bigger. In keeping with
the spirit of your questions, I've written the code to start placing solutions in column D, and wrap around to further columns as
needed. You probably won't need to.

HTH,
Bernie
Excel MVP

Sub SolveIt()
Dim A As Double
Dim B As Double
Dim C As Double
Dim WA As Double
Dim WB As Double
Dim WC As Double
Dim Target As Double
Dim myStep As Double
Dim myCount As Long
Dim ColIndex As Integer

Target = 40
myStep = 1
WA = 4
WB = 2
WC = 1
myCount = 1
ColIndex = 4

Cells(myCount, ColIndex).Value = "Solutions"
For A = Target / WA To 0 Step -myStep
For B = 0 To (Target - (WA * A)) Step myStep
C = Target - (WA * A) - (WB * B)
If C >= 0 Then
myCount = myCount + 1
If myCount > 65536 Then
myCount = 1
ColIndex = ColIndex + 1
End If
Cells(myCount, ColIndex).Value = _
A & ", " & B & ", " & C
Else
GoTo NoMoreB
End If
Next B
NoMoreB:
Next A

End Sub


--

HTH,
Bernie
Excel MVP


Hi all,
I tried a clever way to solve my problem but I couldn't...
Here my problem
I have 3 types of populations with different weights
col A = 4, col B = 2, col C = 1
So one A is equal to 2B or is equal to 4C
So one B is equal to 2C or is equal to 1/2 A
I would like to compute all possible ABC combinations to
reach a target (40 for example)
Example: 10A = 40 but also 5A + 10B or 40C . . .
How can I build a table showing all possible combinations ?
Do somebody has a bright subtle idea ?
Thanks in advance !!!
Joël
 
Joel,

If you need a solution for numbers entered in columns A, B, and C, the code below works the same way as the previous code.

It assumes that row 1 has labels.

Column A should be sorted descending, and columns B and C sorted ascending.

HTH,
Bernie
Excel MVP

Sub SolveIt2()
Dim A As Range
Dim B As Range
Dim C As Range
Dim WA As Double
Dim WB As Double
Dim WC As Double
Dim Target As Double
Dim myValue As Double
Dim myCount As Long
Dim ColIndex As Integer

Target = 40
WA = 4
WB = 2
WC = 1
myCount = 1
ColIndex = 4

Cells(myCount, ColIndex).Value = "Solutions"
For Each A In Range(Range("A2"), Range("A2").End(xlDown))
For Each B In Range(Range("B2"), Range("B2").End(xlDown))
myValue = WA * A.Value + WB * B.Value
If myValue > Target Then GoTo NoMoreB
For Each C In Range(Range("C2"), Range("C2").End(xlDown))
myValue = WA * A.Value + WB * B.Value + WC * C.Value
If myValue = Target Then
myCount = myCount + 1
If myCount > 65536 Then
myCount = 1
ColIndex = ColIndex + 1
End If
Cells(myCount, ColIndex).Value = _
A & ", " & B & ", " & C
Else
If myValue > Target Then GoTo NoMoreC
End If
Next C
NoMoreC:
Next B
NoMoreB:
Next A

End Sub


Hi all,
I tried a clever way to solve my problem but I couldn't...
Here my problem
I have 3 types of populations with different weights
col A = 4, col B = 2, col C = 1
So one A is equal to 2B or is equal to 4C
So one B is equal to 2C or is equal to 1/2 A
I would like to compute all possible ABC combinations to
reach a target (40 for example)
Example: 10A = 40 but also 5A + 10B or 40C . . .
How can I build a table showing all possible combinations ?
Do somebody has a bright subtle idea ?
Thanks in advance !!!
Joël
 
If you need a solution for numbers entered in columns A, B, and C, the code
below works the same way as the previous code.

It assumes that row 1 has labels.

Column A should be sorted descending, and columns B and C sorted ascending.
Click to expand...
...

Or the code could load all 3 cols into arrays and sort them as needed.
Sub SolveIt2()
Dim A As Range
Dim B As Range
Dim C As Range
Dim WA As Double
Dim WB As Double
Dim WC As Double
Dim Target As Double
Dim myValue As Double
Dim myCount As Long
Dim ColIndex As Integer

Target = 40
WA = 4
WB = 2
WC = 1
myCount = 1
ColIndex = 4

Cells(myCount, ColIndex).Value = "Solutions"
For Each A In Range(Range("A2"), Range("A2").End(xlDown))
For Each B In Range(Range("B2"), Range("B2").End(xlDown))
myValue = WA * A.Value + WB * B.Value
Click to expand...

Store this in a different variable and avoid recalcing it inside the For C loop.
If myValue > Target Then GoTo NoMoreB
Click to expand...

Picky: Exit For would accomplish the same thing as this GoTo. Unnecessary GoTos
(any GoTo that requires more lines of code qualify as unnecessary) should always
be avoided.
For Each C In Range(Range("C2"), Range("C2").End(xlDown))
myValue = WA * A.Value + WB * B.Value + WC * C.Value
If myValue = Target Then
myCount = myCount + 1
If myCount > 65536 Then
myCount = 1
ColIndex = ColIndex + 1
End If
Cells(myCount, ColIndex).Value = _
A & ", " & B & ", " & C
Else
If myValue > Target Then GoTo NoMoreC
End If
Next C
NoMoreC:
Next B
NoMoreB:
Next A

End Sub


I would like to compute all possible ABC combinations to
reach a target (40 for example)
Example: 10A = 40 but also 5A + 10B or 40C . . .
Click to expand...
...

As the OP shows, values from one column only could equal the target value, and
should be considered solutions. Your macro only lists combinations involving one
value from each column, so it's not listing all combinations.
 
Back
Top