Question how to compare sum of a few numbers from a set against a given number?

[recyan]

Did not know where to post this, so ended up posting here.
I have a set of numbers, say (these could also be values of a column in a table)

FieldA = { 11, 16, 20, 23, 30, 37, 40, 50 }

I have a number, say 196.

I want {16,23,30,37,40,50} to be returned as these numbers add up to 196.

Note :
1) There is no possibility of two solutions with the kind of numbers that I may be using.
2) A solution using excel is also OK, though, personally I would prefer access.

Edit :
3) {16,23,30,37,40,50} - Each value is a separate record i.e. they are not in a single field, rather :
16
23
30
37
40
50

Can I request some guidance ?

Edit :
Note :
Am casting the net wide.
Have posted this here http://www.accessforums.net/access/how-compare-sum-few-numbers-set-against-29593.html#post144820 also.
In case there are any responses there, will update here.


Thanks

 

[John Big Booty]

I guess you'd need to build a recursive loop that works it's way through all the possible combinations of your values until it gets a match on your target value.


...and please don't ask me how you'd do that. I know that in theory, that is what you need to do, but putting it into practice; I've got no idea how you'd achieve it

 

[Pat Hartman]

I also have no idea how to solve this problem efficiently but I would start by putting the elements into an array and sorting it descending. I would subtract the values from the target rather than adding them and comparing to the target. this will require less manipulation since you will always have a current value of what is remaining and so could exit the loop when the remaining value is too low to be satisfied by anything remaining in the array.

 

[recyan]

Hi John & Pat,
Thanks for replying.
I too concluded that perhaps the solution would lie somewhere in the direction of what John has suggested, the keyword "combinations" of "Combinations & Permutations" & "arrays" as Pat has suggested.


Get all the combinations possible in arrays.
Then,
loop thro each array
and
sum elements of each array & compare it with the given number.
Guess it will need some effort on my part with VBA( am pretty low on the scale with it).
Hope it is as simple as I make it sound.
Though currently, the need for solution for this, has gone,
Will post solution, if I manage to make the function.

Once again Thanks.

 

[John Big Booty]

I probably start by checking;

1. Are the total payments; more, less or equal to the expected Total
2. Does any single, payment cover the total
3. and here's where the recursive nature of things kicks in, check if any combination of two payments covers the total and so on until you have parity.

 

[BigHappyDaddy]

I have to admit I was interested to see if anyone could other than brute force. I am still hopeful.

 

[MarkK]

Here's a class module solution, where each instance of the class, if it fails to reach the limit, creates the next instance, and if the next fails, and so on... If the limit is exceeded, the instance that exceeds the limit passes control back to the previous instance, which advances the current record in its disconnected recordset. And so on. Simple. Fast. Etc...

And there's an easy little interface to plug the numbers in and make it go.

Took me three hours.

 

[recyan]

To all those who might be interested, my current thought status in crude pseudo-code ( real crude).

a = input number to be compared;

sqlAllchecknumbers = select testID, checknumbers from table1 where checknumbers <= a order by checknumbers;

rst = sqlAllchecknumbers;

b = rst!checknumbers;
c = rst!testID;
d = recordCount(rst)
Array results() = rst(checknumbers)

while not rst.eof or rst.bof 
	if ( b == a) {
		print "The checknumber matching is " & b;
		print "The corresponding ID is " & c;
		e = "OK";
		exit;
	}
loop

if ( e <> "OK" ) {
	' get combinations starting with 2 numbers (since we have already checked for 1 number each) 
	' till max count of records i.e. d
	' and check sum of elements in each combination against input number i.e. a
	
	For ( f = 2, f <= d, f = f + 1 ) {
		' the combinations formula - G - the number of combinations possible
		' G(y,z) = y!/((y-z)!*z!) - in our case, z = f & y = d
		' use of seperate factorial function
		' use of separate Combination function to display combinations
		
		G = d! / ( ( d - f )! * f! );
		
		h = 0
		for (h = 1, h <= G, h = h + 1)	{
			array combinationResult = get the Combination in array; 
			for (i = 0, i < ubound(combinationResult) ) {
				sum = sum + combinationResult[i]
			}
			
			if ( sum == a) {
				print array combinationResult;
				exit everything;
			}
		} 
	}
}

Thanks

Edit : Sorry lagbolt, missed your post earlier. Will take a look & revert.

 

[mahenkj2]

Thanks lagbolt for such a good solution. As OP said that there will always be a single opportunity of sum, it seems to satisfy the requirement.

Only thing I observed is Access is crashing sometimes on pressing GO, I do not know why?

 

[recyan]

@lagbolt,
Thanks, it appears to work perfectly, the way I wanted.
I am not facing the problem that mahenkj2 is facing (crashing sometimes). It could perhaps be my limited testing ability.
Haven't got down to understanding the code.
Only one question, is the code in "cNumber" the only thing or are there some other things that I need to look at, to understand things?

Thanks

Edit : Can't rep. Get message "need to spread some around". Where do we see whom we have repped or thanked earlier ?

 

[John Big Booty]

...

Edit : Can't rep. Get message "need to spread some around". Where do we see whom we have repped or thanked earlier ?

I don't believe there is any way of seeing who you have rep'd recently

 

[recyan]

Hi John,

I still can't rep lagbolt.
Still get the message - "You need to spread some ....."
It's now more than 30 days, since 3rd Nov.
Is there some way, you could check this out ?
The odd part is, I am able to rep others.

Sorry for the trouble.

Thanks

 

[John Big Booty]

Like the message says, you need to rep a few other people before you can Rep Lagbolt again. Stops people SPAMMING one user with rep or de-rep.