Алгоритм рассадки групп людей?

Question

Мне интересно написать приложение, которое может определить, как разместить группы из 2-10 человек за столами, которые могут вместить 10 человек.Там будет около 15 столов и 140 человек.Я не хочу разбивать какие-либо группы людей.

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

Answer 1

Это проблема упаковки бункера .

Answer 2

Это просто вариант стандартной задачи " Рюкзак "

Answer 3

Это проблема упаковки бункера , которая является NP-Hard (нелегко найти лучший ответ, и нелегко проверить, является ли ответ лучшим).

Группы людей представляют собой отдельные объекты, причем объем = количество людей в группе. Столы - это мусорные ведра размера 10.

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

Однако ваша проблема смягчена (в некотором смысле), потому что у вас есть 10 столов, то есть вы не пытаетесь разместить людей на минимальном количестве столов. Если 10 таблиц является ОПТИМАЛЬНЫМ решением, у вас будут проблемы с поиском решения (если оно вообще существует), но если оптимальное значение действительно 7 или 8, найти решение будет легко. Все зависит от групповых распределений.

Answer 4

Когда у нас была эта проблема в школе, мы решили ее как проблему TSP.