Алгоритм выбора значений из набора, чтобы соответствовать целевому значению?

Question

У меня есть фиксированный массив постоянных целочисленных значений длиной около 300 элементов (набор A). Цель алгоритма - выбрать два числа (X и Y) из этого массива, которые соответствуют нескольким критериям на основе ввода R .

Формальное требование:
Выберите значения X и Y из набора A так, чтобы выражение X * Y / (X + Y) было как можно ближе до R .

Это все, что нужно сделать. Мне нужен простой алгоритм, который сделает это.

Дополнительная информация:
Набор A можно заказать или сохранить любым способом, в конечном итоге он будет жестко запрограммирован. Кроме того, с небольшим количеством математики, можно показать, что лучшее Y для данного X является ближайшим значением в Set A к выражению * * тысяча тридцать-одна Х * Р / (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 найдите ближайшее значение R в B, используя бинарный поиск, а затем выберите соответствующие X и Y.

Я предполагаю, что наличие массива B (с информацией X & Y) не будет большой проблемой памяти и может быть легко закодировано (используя код для написания кода!: -)).

Это будет достаточно быстро: в худшем случае ~ 17 сравнений.

---

Решение 2)

Возможно, вы также можете сделать следующее (не пытался это доказать, но кажется правильным):

Вести массив значений 1 / X, отсортированных.

Теперь, учитывая R, вы пытаетесь найти ближайшую сумму к 1 / R с двумя числами в массиве 1 / X.

Для этого вы поддерживаете два указателя на массив 1 / X, один наименьший и один на самый большой, и продолжаете увеличивать один и уменьшать другой, чтобы найти ближайший к 1 / R. (Это классический вопрос для собеседования: найдите, если в отсортированном массиве есть два числа, сумма которых равна X)

Это будет O (n) сравнений и дополнений в худшем случае. Это также подвержено проблемам с точностью. Вы можете избежать некоторых проблем с точностью, если будете поддерживать отсортированный в обратном порядке массив X.

Answer 2

Мне приходят в голову две идеи:

1) Так как множество A является постоянным, некоторая предварительная обработка может быть полезной. Предполагая, что диапазон значений A не слишком велик, вы можете создать массив размером N = max (A). Для каждого индекса i вы можете хранить ближайшее значение от A до i. Таким образом, вы можете улучшить свой алгоритм, найдя ближайшее значение в постоянном времени, вместо использования бинарного поиска.

2) Я вижу, что вы опускаете X <= R, и это правильно. Если вы определите, что X <= Y, вы можете еще больше ограничить диапазон поиска, поскольку X> 2R также не даст никаких решений. Таким образом, диапазон для сканирования составляет R

Answer 3

Когда размер входных данных (приблизительно) постоянен, решение O (n * log (n)) может работать быстрее, чем конкретное решение O (n).

Я бы начал с решения, которое вы понимаете лучше всего, и при необходимости оптимизировал бы его.