Algorithm to pick values from set to match target value?
Posted
by CSharperWithJava
on Stack Overflow
See other posts from Stack Overflow
or by CSharperWithJava
Published on 2010-05-25T16:52:37Z
Indexed on
2010/05/25
21:51 UTC
Read the original article
Hit count: 231
I have a fixed array of constant integer values about 300 items long (Set A). The goal of the algorithm is to pick two numbers (X and Y) from this array that fit several criteria based on input R.
Formal requirement:
Pick values X and Y from set A such that the expression X*Y/(X+Y) is as close as possible to R.
That's all there is to it. I need a simple algorithm that will do that.
Additional info:
The Set A can be ordered or stored in any way, it will be hard coded eventually. Also, with a little bit of math, it can be shown that the best Y for a given X is the closest value in Set A to the expression X*R/(X-R). Also, X and Y will always be greater than R
From this, I get a simple iterative algorithm that works ok:
int minX = 100000000;
int minY = 100000000;
foreach X in A
if(X<=R)
continue;
else
Y=X*R/(X-R)
Y=FindNearestIn(A, Y);//do search to find closest useable Y value in A
if( X*Y/(X+Y) < minX*minY/(minX+minY) )
then
minX = X;
minY = Y;
end
end
end
I'm looking for a slightly more elegant approach than this brute force method. Suggestions?
© Stack Overflow or respective owner