Распределение мест в python

Question

У меня есть набор групп с фиксированным количеством человек для каждой группы:

Группа1: 10 Группа2: 20 Группа3: 18 Группа4: 10

и набор свободных мест на Комната, в которой могла бы разместиться каждая неделимая группа :

Комната1: 10 Комната2: 38 Комната3: 10

Результатом должно быть возможное назначение групп в комнатах с учетом количество человек в каждой группе не подлежит разделению. вывод: Например:

Group1->Room1
Group2->Room2
Group3->Room2
Group4->Room3

Как я могу решить эту проблему в python? есть какой-то код, который можно было бы использовать для этого сценария? конечно, моя проблема сложнее, чем представленная (она описана как простой случай, просто чтобы иметь представление)

Спасибо

Answer 1

Я думаю, что самая важная часть - это начать с формулирования математической модели проблемы. Вот моя версия:

This is basically a variation on the standard assignment problem.

This can be implemented easily with any Mixed-Integer Programming (MIP) or Constraint Programming (CP) solver.

Showing code is not as useful as the above model, but just as an illustration, here is an implementation using a simple CP solver (https://pypi.org/project/python-constraint/).

from constraint import *

#
# data
# group sizes and room capacities
#
groups = {"Group1": 10, "Group2": 20, "Group3": 18, "Group4": 10}
rooms = {"Room1": 10, "Room2": 38, "Room3": 10}

#
# constraint problem
#
# variables:
#      x[i,j] = 1 if group i is assigned to room j
#               0 otherwise
# constraints:
#     sum(j, x[i,j]) = 1                     for all i   assign each group to exactly one room
#     sum(i, size[i]*x[i,j]) <= capacity[j]  for all j   capacity constraint
# 
problem = Problem()
problem.addVariables(["x_%s_%s" %(i,j) for i in groups for j in rooms],[0,1])
for i in groups:
  problem.addConstraint(ExactSumConstraint(1),["x_%s_%s" %(i,j) for j in rooms])
groupSizes = [groups[i] for i in groups]
for j in rooms:
  problem.addConstraint(MaxSumConstraint(rooms[j],groupSizes),["x_%s_%s" %(i,j) for i in groups])
                        
S = problem.getSolutions()

Здесь напечатаны все возможные решения. Всего их два:

[{'x_Group1_Room1': 1,
  'x_Group1_Room2': 0,
  'x_Group1_Room3': 0,
  'x_Group2_Room1': 0,
  'x_Group2_Room2': 1,
  'x_Group2_Room3': 0,
  'x_Group3_Room1': 0,
  'x_Group3_Room2': 1,
  'x_Group3_Room3': 0,
  'x_Group4_Room1': 0,
  'x_Group4_Room2': 0,
  'x_Group4_Room3': 1},
 {'x_Group1_Room1': 0,
  'x_Group1_Room2': 0,
  'x_Group1_Room3': 1,
  'x_Group2_Room1': 0,
  'x_Group2_Room2': 1,
  'x_Group2_Room3': 0,
  'x_Group3_Room1': 0,
  'x_Group3_Room2': 1,
  'x_Group3_Room3': 0,
  'x_Group4_Room1': 1,
  'x_Group4_Room2': 0,
  'x_Group4_Room3': 0}]