Разработка алгоритма: можете ли вы найти решение проблемы с рюкзаком, если нет ограничения по максимальному весу? - PullRequest
0 голосов
/ 18 октября 2019

Я не могу найти подходящий алгоритм для моей проблемы. Моя проблема заключается в следующем: Есть n задач. Каждое задание повторяется разное количество раз. Две реплики одной и той же задачи не должны находиться на одном агенте. назначьте реплики агенту так, чтобы сумма реплик на каждом агенте была примерно одинаковой. Для агента нет ограничения по весу.
это можно решить с помощью рюкзака?

1 Ответ

0 голосов
/ 18 октября 2019

Задача ранца без весов - это просто сортировка по убыванию по значению и взятию столько, сколько вам нужно. Так что это не имеет особого смысла без ограничения веса - потому что теперь оптимизация не требуется.

Я также не вижу здесь никакой связи с вашими агентами.

Проблема довольно проста для решения:

  1. Сортировка агентов по возрастанию по длине их очередей
  2. и передача следующей работы первой, у которой еще нет копии этой задачи.
  3. repeatпока все задачи не назначены
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...