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

我认为最重要的部分是从建立问题的数学模型开始。以下是我的版本：

这基本上是标准分配问题的一个变体

这可以通过任何混合整数规划（MIP）或约束规划（CP）求解器轻松实现

显示代码没有上面的模型有用，但作为一个示例，这里是一个使用简单CP解算器（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}]