Possible Combination with same Total

B

botyok

Hello,


Need help in coding this problem in microsoft access.


I have a table with values 1,2,6,7,9,11,15. These values are taken from
between 1 to 50, no the same value on the table.



What i would like to implement is from a given total, the code pick 4
numbers and give the possible combination with the same total of the given
total. No number should be picked repeatedly in the 4 numbers. No repeat of
combinations ex. 6,9,11,7 = 33 11,9,6,7 = 33

ex.

value of give total = 33

possible combinations (numbers in any position): No number should be picked
repeatedly in the 4 numbers. No repeat of combinations ex. 6,9,11,7 = 33
11,9,6,7 = 33 7,9,11,6 = 33 6,11,7,9 = 33

correct way is:


6,9,11,7 = 33
1,6,11,15 = 33
and so on...

Any help is highly appreciated.


botyok
 
J

John W. Vinson

Hello,


Need help in coding this problem in microsoft access.


I have a table with values 1,2,6,7,9,11,15. These values are taken from
between 1 to 50, no the same value on the table.



What i would like to implement is from a given total, the code pick 4
numbers and give the possible combination with the same total of the given
total. No number should be picked repeatedly in the 4 numbers. No repeat of
combinations ex. 6,9,11,7 = 33 11,9,6,7 = 33

ex.

value of give total = 33

possible combinations (numbers in any position): No number should be picked
repeatedly in the 4 numbers. No repeat of combinations ex. 6,9,11,7 = 33
11,9,6,7 = 33 7,9,11,6 = 33 6,11,7,9 = 33

correct way is:


6,9,11,7 = 33
1,6,11,15 = 33
and so on...

Any help is highly appreciated.
Click to expand...

This is a variant of the "Knapsack Problem", which has been shown to be
NP-Complete - that is, a problem without a closed-form solution. For four
numbers an exhaustive search of all possible combinations is not totally out
of range... but for 100 you'll be waiting for a LONG time.

A brute force query would involve a self join:

SELECT A.val, B.val, C.val, D.val, A.val+B.val+C.val+D.val As TheSum
FROM yourtable AS A, yourtable AS B, yourtable AS C, yourtable AS D
WHERE B.val > A.val AND C.val > B.val AND D.val > C.val
AND A.val+B.val+C.val+D.val = 33;

You don't lose any generality by having the > operators, since the Cartesian
join will give you all possible combinations; the criterion will limit it to
the single combination where the values are in ascending order.
 
J

John Spencer

This might be a small improvement in speed on John's solution. Depending on
the number of records in the table and the result desired I saw speed
differences of 3 to 5 times. And as John said, this gets slower very quickly
as the number of values in the table increases.

If the value you are looking for is always larger than any value in the table
then you can remove the check on max value of the source fields.

Also, make sure your source fields are indexed.

PARAMETERS [Total?] Long;
SELECT Ia.IntegerField, Ib.IntegerField, Ic.IntegerField, Id.IntegerField,
Ia.IntegerField+Ib.IntegerField+Ic.IntegerField+Id.IntegerField AS Result
FROM ((IntegerTable_Pop AS Ia INNER JOIN IntegerTable_Pop AS Ib ON
Ia.IntegerField < Ib.IntegerField) INNER JOIN IntegerTable_Pop AS Ic ON
Ib.IntegerField < Ic.IntegerField) INNER JOIN IntegerTable_Pop AS Id ON
Ic.IntegerField < Id.IntegerField
WHERE Ia.IntegerField <= [Total?]
AND Ib.IntegerField <= [Total?]
and Ic.IntegerField<= [Total?]
and Id.IntegerField<= [Total?]
AND Ia.IntegerField+Ib.IntegerField+Ic.IntegerField+Id.IntegerField = [Total?]
ORDER BY Ia.IntegerField, Ib.IntegerField, Ic.IntegerField, Id.IntegerField;

You will need to substitute your field and table names for IntegerTable_Pop
and IntegerField.

John Spencer
Access MVP 2002-2005, 2007-2008
The Hilltop Institute
University of Maryland Baltimore County
 
Top