Задача в нахождении паретооптимального множества решений?
Допустим, есть вектор характеристик (п1, п3, м) и нужно найти решения, где п1 и п3 максимальны, а М минимально.
Каждая пара решений(р1, р2) может находиться в трех состояниях:
1) р1 по всем параметрам лучше р2
2) р2 по всем параметрам лучше р1
3) р1 и р2 векторно несравнимы (когда часть параметров одного решения лучше, а часть хуже). Пример (item1, item5).
Можно за nlogn оставить векторно несравнимые решения двойным циклом. Во внешнем цикле брать строку из таблицы, а во внутреннем сравнивать взятую строку со всеми последующими, удаляя те, которые проигрывают по всем характеристикам. После завершения цикла останется паретооптимальное множество решений.
P.S. в свое время мне помогла книга
Подиновский В.В., Ногин В.Д. Парето-оптимальные ре...
UPD. Полное решение.
Алгоритм.
Пусть у нас есть N записей (будем называть их n1, n2, ...), каждой из которых ставится в соответствие вектор характеристик (a,b,c), где a - param1, b - param2, c - money.
Есть ограничение minmax на a, b и max на c.
Шаг 1.
Для каждой отдельно взятой записи определяем количество, больше которого мы не можем взять (назовем его max(n)).
Пример. Если у нас есть запись (5, 10, 10), minmax(a) = (40, 80), minmax(b) = (50, 70), max(c) = 60, то
Определям количество.
max(a): 80 / 5 = максимум 16 записей
max(b): 70 / 10 = максимум 7 записей
max(c): 60 / 10 = максимум 6 записей
То есть из всех верхних ограничений следует, что мы можем взять эту запись не более 6 раз. max(n) = 6
Строки с max(n)=0 удаляем.
Шаг 1.1 (опциональный). Позволяет отловить решение, удовлетворяющее всем условиям быстрее, но не обязательно выдаст самое эффективное.
Для каждой записи сделаем проверку по минимальному условию min(n). В качестве примера возьмем запись из прошлого примера.
min(a): 40 / 5 = минимум 8 записей
min(b): 50 / 10 = минимум 5 записей
По совокупности ограничений понимаем, что мы можем взять минимум 8, а максимум 6 записей для составления решения
только из нескольких этих записей, что невозможно. Если бы мы получили результат, где min(n) <= max(n), то могли бы построить допустимые решения,
состоящие из одной записи.
Шаг 2. Составление комбинаций из записей.
Представим, что у нас есть чудесное выражение вида k1*n1 + k2*n2 + ... + kN*nN = (ak, bk, ck)
Диапазон для перебора каждого k_i = (0, max(n_i))
Помним, что n_i - это вектора. Соответственно, результат выражения - это сумма векторов, каждый из которых домножен на свой коэффициент.
Все те коэффициенты, при которых (ak, bk, ck) удовлетворяют minmax на ak, bk и max на ck мы сохраняем как допустимые.
Все :)
Средний
