Best Possible Combination

[G Gabriel]

The scenario is:
A table has a numeric field which has values ranging from .01 to 10,000. there is no rhyme or reasons to these values.
A user inputs a value, say in a variable.
How to find the combination of different values from the table, the sum of which is equal to or closest to but not more than the value entered by the user?
There is another wrinkle to this: the optimal solution is one that finds the least number of values that make up the desired sum.
I came up with a concept for a function to do that (I will share the concept shortly) but something in the back of my mind tells me I must be missing or forgetting some algebraic concept that optimizes this solution.

Any and all ideas are welcome and appreciated.
Thanks.

[Tom Cone Jr]

Re: Best Possible Combination

Looking for pairs only? Or can the sum be the result of 3 or more values?

[G Gabriel]

Re: Best Possible Combination

Any number of values.

[Mike Wilson]

Re: Best Possible Combination

How many records in the table?

[G Gabriel]

Re: Best Possible Combination

Hundreds. Could be more.

[Al Buchholz]

Re: Best Possible Combination

ideas - eliminate impossibilities

1. if the sum of 2 or more numbers is less than a given number ,then you should only look at numbers in the table that are less than the given number. ( I'm thinking zeroes aren't in this table..)

2. then I'd look at the largest numbers first to find another number that add to the given number - then start looking for the more than 2 numbers summed..

3. in looking for the second number, look at only the numbers that are equal to or less than the difference of the 1st number and the given number.

[G Gabriel]

Re: Best Possible Combination

Al:
Pretty much what I am thinking:
1-Sorted the table in descending order eliminating values > the user's number
2-Subtract the top value from the user's
3-Re-query/sort the table for a number equal the difference.
4-Log the difference and tag the loop
5-Re-run
6-Sort the log for the least difference
That's my operating concept.

[Mike Wilson]

Re: Best Possible Combination

so far I have this to build a test table ("nums"), if it helps anyone

 dim vcn as c
dim vcn1 as C
 dim vm as n

dim t as p
t=table.open("nums")
'Turn on the hourglass cursor.
hourglass_cursor(.t.)
for i = 1 to 1000
	NEWNUM:
	vm=val(right(alltrim(str(rand()*1000,5)),1))
	vcn1=left(alltrim(str(rand()*100000000,9)),vm)
	if len(vcn1)>6
		GOTO NEWNUM
	else if val(vcn1)=0
		GOTO NEWNUM
	end if

	if len(vcn1)<3
		vcn="."+padl(vcn1,2,"0")
	else
		vcn=substr(vcn1,1,len(vcn1)-2)+"."+right(vcn1,2)
	end if
	'msgbox(vcn1,vcn+crlf()+str(vm))
	
	t.enter_begin()
	t.t_val=val(vcn)
	t.enter_end(.t.)
next

hourglass_cursor(.f.)

[G Gabriel]

Re: Best Possible Combination

I thought I was missing some algebraic/math concept. Evidently not.
With a quick search I found out that this falls under what is know in math as "NP-complete" (nondeterministic polynomial) i.e. a math puzzle that cannot be solved with any logical algorithm, i.e. one in which you cannot guess what the right solution is hence you cannot design one. Therefore, when you try to write a routine to solve it, you could only use brute force. So the best I could do is to reduce the brutality.

[Ted Giles]

Re: Best Possible Combination

Have a look at the Linear Programming discussion for Excel.
This is probably what you want;

Maximize: cTx
Subject to: Ax ≤ b.

The theory gets a bit deep but essentially it's all about optimisation.

[G Gabriel]

Re: Best Possible Combination

Thanks Ted.
I have played with Excel Solver in the past, but to my knowledge there is no equivalent in alpha.
The odd thing is, 30 yrs ago or so when I started playing with spreadsheets.. there was a program called "What is Best", yes back on those stone ages. I used it for similar purposes. There are tons of optimization software out there, but in alpha you have to design your own scheme. It would be a nice add-on.

[Ted Giles]

Re: Best Possible Combination

I agree, but it's likely to be of limited use I suspect.
Is there not a BASIC function in VB you could swipe and use?

[Mike Wilson]

Re: Best Possible Combination

So Gabriel,
Have you got it ground out yet. I'm still working on it. Pretty interesting and complex puzzle.

[G Gabriel]

Re: Best Possible Combination

Ted:
I could do this easily in Excel with or without VB. I wanted to do this in alpha. Yes, an add-on would be of limited use, but imagine the benefits of optimization in so many industries/businesses.

Mike:
I haven't spent a whole lot of time on development, only a concept and stopped in hope of finding that magical formula which so far I haven't found. Linear programming that Ted refers to is about as close as you can get but there is some differences. In LP, most of the time, you are not given a set of values but rather a set of constraints and an objective from which to determine a set of values, i.e resolve the variables based on the given constraints and objective. In that case you find the intersecting point at the feasibility region with one shot at the Bow. However, if you were given a set of values to choose from and you were to apply LP, at this point you will need to do several permutations but by applying LP you reduce the number of these permutations through one of several means developed by several Math geniuses over the years the most common of which is know as "Simplx".

There is a similarity though between LP & the scenario at hand: The objective of LP is to reduce the number of permutations which is what I intuitively did in my concept.
If you have hundreds, let alone thousands of records, you will be doing calculations of all possible combinations till Kingdom come. My concept First removes the records that cannot possibly work secondly by starting with the larger values first it reduces the number of the combinations and thirdly by testing the difference between the user's value and the combined value and once you get to zero you will quit, no need for any further calculations since you achieved the 2 goals (1-finding the combo closest to the user's 2-with the least number of values) thus reducing the permutations by a fraction which could be a small fraction or a major one. LP in this case is still a brute force in which brute is considerably reduced.

[Al Buchholz]

Re: Best Possible Combination

This may also be a situation where the data should be loaded (after filtering) to an array or a collection so that processing can be done in memory instead of reading and re-reading rows from a table.