Суть задачи.
Есть набор объектов, попарное их сочетание дает определенный числовой выход (вес решения), необходимо из всех перечисленных пар выбрать набор НЕПОВТОРЯЮЩИХСЯ пар с максимальной суммой этих весов.
На входе просто список из 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
Как пример:
Об1 / Об2 = 7
Об1 / Об3 = 6
Об2 / Об3 = 2
Об4 / Об2 = 3
Об4 / Об1 = 5
Правильный выход Об1 / Об3 + Об4 / Об2 = 6 + 3 = 9
Об1 / Об2 = 7
Об1 / Об3 = 6
Об2 / Об3 = 2
Об4 / Об2 = 3
Об4 / Об1 = 5
Правильный выход Об1 / Об3 + Об4 / Об2 = 6 + 3 = 9
- Romeo
- Сообщения: 3126
- Зарегистрирован: 02 мар 2004, 17:25
- Откуда: Крым, Севастополь
- Контактная информация:
Перенесено из WinApi, Shell.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
-
- Сообщения: 1
- Зарегистрирован: 25 фев 2018, 00:39
У нас на сайте очень просто заказать проститутку Москвы нужно лишь позвонить ей и она приедет к вам для незабываемого отдыха.