Мне было поручено объединить студентов в группы (подготовить лагерь программистов), но с несколькими ограничениями. Хотя я выполнил задачу вручную, я хотел бы знать, существуют ли уже некоторые алгоритмы для подобных задач или как я могу разработать такой алгоритм.
Фон : всего 40 учеников с этими атрибутами:
- Пол: F / M
- Оценка: год 1/2
- школа: школа 1 / школа 2 /...
- результат ранней оценки: Ранг от 1 до 40
Ограничения : Все они должны быть удовлетворены.
- Ровно 4 человека в группе
- В каждой группе должна быть хотя бы девушка
- В каждой группе должен быть как минимум студент 2 курса
- 4 члена группы должны быть из 4 разных школ
- В каждой группе должен быть хотя бы один студент, который занял 10 место в ранней оценке
Что я ожидаю :
- Лучшее: существующий алгоритм / программа для такого рода задач
- Или, алгоритм для этой конкретной проблемы
- Или, по крайней мере, некоторые идеи по созданию алгоритма для этой конкретной задачи
Мои мысли :
Поскольку мне удалось создать группы вручную, я знаю, что такое решение действительно существует для моего текущего набора данных. Но если мне нужен алгоритм, чтобы найти решение для меня, он должен сначала попытаться проверить, существует ли решение вообще, проверить, больше ли число девочек / студентов 2-го года, чем 10 (по принципу голубя), и некоторые другие условия , И очевидно, что Constraint 5 является самым простым и может предоставить базовое решение для остальных. Тем не менее, я до сих пор не могу найти систематический способ сделать это. Возможно, брутфорс и рандомизация могут помочь? Я не уверен.
И извините, поскольку данные конфиденциальны, я не могу их опубликовать.
Обновление : после консультации с другом возможный метод:
- Сначала поместите лучшие 1-10 в 10 различных групп.
- Затем перебирайте группы. Если в группе есть только один мальчик / девочка, попробуйте добавить девочку / мальчика из другой школы.
- Затем размер проблемы уменьшается с 2 ^ 40 до 2 ^ 20, что делает bruthforce жизнеспособным решением.