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: 204

Filed under:
|
|
|

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

Related posts about algorithm

Related posts about search