Помогите с оптимальным решением

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы:C_O_D_E, DeeJayC

Ответить
Артем.Зуев
Сообщения:2
Зарегистрирован:27 июл 2017, 10:31

27 июл 2017, 10:40

Суть задачи.

Есть набор объектов, попарное их сочетание дает определенный числовой выход (вес решения), необходимо из всех перечисленных пар выбрать набор НЕПОВТОРЯЮЩИХСЯ пар с максимальной суммой этих весов.

На входе просто список из 3-х элементов:
Об1 / Об2 / Рез1
Об1 / Об3 / Рез2
Об3 / Об2 / Рез3
Об1 / Об4 / Рез4
...

Полной матрицы пересечений нет, т.е. если всего задействовано 4 объекта, это не значит, что пар 12 (16 - 4), пар может быть и меньше.

Основная цель - решение на node.js с МАКСИМАЛЬНОЙ скоростью, т.к. этот блок - часть высоконагрузочной системы и прямой перебор сочетаний выходит за рамки отводимые на выполнение (для 50 пар время выполнения не должно превышать в среднем 1мс)
Артем.Зуев
Сообщения:2
Зарегистрирован:27 июл 2017, 10:31

27 июл 2017, 10:44

Как пример:

Об1 / Об2 = 7
Об1 / Об3 = 6
Об2 / Об3 = 2
Об4 / Об2 = 3
Об4 / Об1 = 5

Правильный выход Об1 / Об3 + Об4 / Об2 = 6 + 3 = 9
Аватара пользователя
Romeo
Сообщения:3091
Зарегистрирован:02 мар 2004, 17:25
Откуда:Крым, Севастополь
Контактная информация:

27 июл 2017, 15:47

Перенесено из WinApi, Shell.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
oloko.ivanova
Сообщения:0
Зарегистрирован:25 фев 2018, 00:39

25 фев 2018, 00:40

У нас на сайте очень просто заказать проститутку Москвы нужно лишь позвонить ей и она приедет к вам для незабываемого отдыха.
Ответить