Распределение ресурсов w.r.t. индивидуальная вместимость - это проблема ранца?

Question

У меня проблема в следующем:

1. У меня мало офисов и ресурсов с разными возможностями (целые числа).
2. Я хочу распределить все ресурсы по разным офисамместоположения, чтобы найти лучший способ разделить их почти поровну между местоположениями так, чтобы возможности всех офисных местоположений были максимально сбалансированы.Несколько вещей, которые нужно иметь в виду:

• Разница между количеством ресурсов в каждом офисе не должна превышать одного.• Возможности каждого местоположения офиса (достигаемые путем добавления отдельных возможностей) должны быть практически равны друг другу.

Я провел исследование в Интернете и узнал об алгоритме рюкзака и алгоритме Bin-pack, который звучитблизко к этой проблеме.

Пример: Количество офисов = 3;Количество человек = 8;Потенциал сотрудников = 10, 20, 5, 150, 90, 200, 250, 140 (значения возможностей 8 ресурсов);

Приведенные выше цифры являются лишь примерами.Он может возрасти до 1000+ для ресурсов и соответствующих значений возможностей.Количество офисов тоже можно варьировать.

Я не запустил часть программирования, если не уверен, что путь, по которому я иду, будет правильным.Я прошу вашей помощи, чтобы направить меня в правильном направлении, чтобы решить эту проблему.

Кроме того, если вы можете поделиться вероятным псевдокодом для этого, будет отличная помощь.

Спасибо!

Answer 1

Это проблема ранца или, по крайней мере, такая же сложная (рассмотрим случай, когда есть только два офиса), поэтому найти лучшее решение будет очень сложно. Вы можете попробовать использовать некоторую общую эвристическую оптимизацию, например, имитированный отжиг: http://en.wikipedia.org/wiki/Simulated_annealing