1

Тема: Максимизировать количество пар, удовлетворяющих заданному ограничению

Даны n числовых значений: x1, x2, ... , xn
                                              y1, y2, ... , yn
и некоторое положительное число eps>0.
Цель: максимизировать количество пар {xi, yj}, удовлетворяющих ограничению: |xi - yj| <= eps (абсолютное значение разности между числами этой пары не превосходит заданного числа eps), причём если число уже использовалось в какой-то паре, то его повторно использовать нельзя, и найти множество таких пар.

PS: как одно из решений этой задачи - я просто генерировал все перестановки чисел 1, 2, ... , n. А дальше просто сопоставлял каждой такой перестановке множество из n пар, выбирая из них лучшее. Но для больших n естественно работает очень долго.
Подскажите, если несложно, более быстрый алгоритм для нахождения подобного множества (может здесь можно как-нибудь использовать алгоритмы, связанные с нахождением максимального паросочетания?)

2

Re: Максимизировать количество пар, удовлетворяющих заданному ограничению

Конечно парасочетания.
Делаешь две доли (доля-x, доля-y).
Делаешь ребро между двумя вершинами,если они подходят под описанное ограничение(|xi - yj| <= eps).
Теперь тебе нужно найти в данном графе максимальное парасочетание.
На этом сайте описано много алгоритмов для нахождения.
Например будет удобно использовать
Метод Куна