Наиболее эффективное расположение сидений

Question

Есть n (n < 1000) группы друзей, размер группы которых характеризуется массивом A[] (2 <= A[i] < 1000). Таблицы присутствуют так, что они могут вместить r(r>2) человек за раз. Каково минимальное количество таблиц, необходимых для размещения каждого, при условии, что для каждого человека должен быть другой человек из своей группы, сидящий за своим столом.

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

Answer 1

та же проблема, что и рюкзак проблема это NP полный (смотрите https://en.wikipedia.org/wiki/Bin_packing_problem). Поэтому найти оптимальное решение довольно сложно.

Эвристический, который работает большую часть времени:

1. Сортировка по группам уменьшения размера.

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

Answer 2

Учитывается ли модель смешанного целочисленного программирования?

Некоторые замечания по этой формулировке:

• Я использовал случайные данные для формирования групп.
• x (i, j) - количество людей группы i, сидящих за столом j.
• x (i, j) представляет собой полуцелую переменную, то есть: это целочисленная переменная со значениями нуля или между LO и UP. Не все решатели MIP предлагают полунепрерывные и полуцелые переменные, но это может пригодиться. Здесь я использую его для обеспечения того, чтобы по крайней мере 2 человека из одной группы должны были сидеть за столом. Если решатель не предлагает эти типы переменных, мы можем сформулировать эту конструкцию, используя также дополнительные двоичные переменные.
• y (j) - двоичная переменная (0 или 1), указывающая, используется ли таблица.
• Уравнение емкости несколько умное: если таблица не используется (y (j) = 0), ее емкость сводится к нулю.
• Опция optcr = 0 указывает, что мы хотим решить оптимальность. Для больших, трудных проблем мы можем остановиться на 5%.
• уравнение заказа гарантирует, что мы начнем заполнять таблицы из таблицы 1. Это также уменьшает симметрию проблемы и может ускорить время решения.
• приведенная выше модель (с 200 группами и 200 потенциально используемыми таблицами) генерирует проблему MIP с 600 уравнениями (строками) и 40k переменными (столбцами). Имеются 37k целых переменных. С хорошим решением MIP мы находим проверенное оптимальное решение (с 150 таблицами) менее чем за минуту.
• Обратите внимание, что это, конечно, не проблема ранца (как предложено в другом ответе - проблема с рюкзаком имеет только одно ограничение), но она напоминает проблему упаковки корзины.

Answer 3

Ваш подход работоспособен.Если существует решение для заданного числа таблиц, тогда существует решение, в котором вы разделили каждую группу на некоторое количество двух и несколько трёх. Сначала разделите три части каждой группы нечетных размеров. У вас остался куча групп ровного размера. Затем разделите два члена каждой группы, размер которых не делится на шесть. И забудьте, что это одна большая группа; разделил его на кучу групп из шести человек.

На данный момент вы разделили все свои группы на несколько чисел, несколько тройки и некоторое количество шестеренок. Дайте каждой таблице нечетный размер один три, раскалывая шесты по мере необходимости; теперь все таблицы имеют размер. Все оставшиеся шестерни теперь можно разделить на два и посадить произвольно.