从set中选择值以匹配目标值的算法？

Question

我有一个固定的常数整数值数组,大约300项(Set A).该算法的目标是从该数组中选择两个数字(X和Y),这些数字符合基于输入R的若干标准.

正式要求:
选值X和ÿ从设置甲使得表达式X*Y /(X + Y)是尽可能接近到ř.

这里的所有都是它的.我需要一个简单的算法来做到这一点.

附加信息:
Set A可以任何方式订购或存储,最终将进行硬编码.此外,通过一些数学运算,可以证明给定X的最佳Y是集合A中最接近表达式X*R /(XR)的值.此外,X和Y总是大于R.

从这里,我得到一个简单的迭代算法,可以正常工作:

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

我正在寻找一种比这种蛮力方法更优雅的方法.建议？

Answer 1

对于可能"更优雅"的解决方案,请参阅解决方案2.

解决方案1)

为什么不创建所有可能的300*300/2或(300*299/2)可能的R 精确值,将它们排序为数组B说,然后给出一个R,找到B中最接近R的值使用二进制搜索,然后选择相应的X和Y.

我认为拥有数组B(带有X和Y信息)不会是一个很大的内存占用,并且很容易被硬编码(使用代码编写代码!:-)).

这将是相当快的:最坏情况~17比较.

解决方案2)

您也可以执行以下操作(未尝试证明,但似乎正确):

保持1/X值的数组,排序.

现在给出一个R,你试着在1/X数组中用两个数字找到最接近1/R的和.

为此你保持两个指向1/X数组的指针,一个指向最小值,一个指向最大值,并保持递增1并递减另一个指针以找到最接近1/R的指针.(这是一个经典的访谈问题:查找排序数组是否有两个数字相加到X)

在最坏的情况下,这将是O(n)比较和添加.这也容易出现精确问题.但是,您可以通过维护反向排序的X数组来避免一些精度问题.