在变量的s的基础上找到变量的组合

Question

我想用Python解决一个问题（就像一个编程谜语）。这不是一个练习或任何与此相关的事情，而是我想找到一个解决办法。在

问题描述：

• 假设我的公司有10个不同的工作岗位。在
• 每个位置都有几个不同的子位置。例如（攻击性，放松，正常）。但是，每个职位的子职位并不相同。其他有1个，其他有2个，其他3个。在
• 我有20个人，每个职位都有他们的表现分数。在

企业生产的最终得分将是每个岗位的得分之和。我想找到得分最高的组合。在

一些想法：

• 因为就业人数不会少于所有的人。在
• 我不能让两个人处于同一位置。在
• 我的第一次尝试是在每个人中取最高分，然后逐一填补所有职位。但这最终带来了一个问题。类似于旅行推销员的问题。在

那么，我的下一个选择是什么？有没有Python实现的想法？在

编辑：更多关于Python的细节

positionslist = [pos1, pos2, pos3, pos4, pos5, pos6, pos7, pos8, pos9, pos10]
subpositions = {"pos1":["A","B"], "pos2":["B","C"],"pos3":["A","B","C"],"pos4":["A"],"pos5":["A","B"],"pos6":["A","B","C"],"pos7":["B"],"pos8":["C"],"pos9":["A","C"],"pos10":["A"]

peoplelist = [{"pos1 A":15,"pos1 B": 8, "pos2 B": 2, "pos2 C": 4, "po3 A": 2, "pos3 B":5...}, {"pos1 A":1, "pos1 B":23,"pos2 B":11,.....},.........]

#run the code

print "best combination:" result

best combination:
pos1 B, person 3, score 23
pos2 C, person 5, score 11
pos3 A, person 18, score  ..
pos4 
pos5
pos6
pos7
pos8
pos9
pos10
Total Score: ....

如前所述，我在伪代码中的实现是：

^{pr2}$

然而，这类似于旅行商问题，最终得到的组合不是最高的。在

Answer 1

这个问题称为二部图中的最大值matching，或assignment problem。由Hungarian algorithm完成。在

在维基百科页面上，implementations有不同的语言。有一个实现的python库munkres。在

Answer 2

如果我读对了，每个人在每个职位上都有一个不同的分数，你想找到所有人和职位的最高分数，也就是说，你必须计算每个职位的每个人的分数。在

我想不出一种表达这一点的方法，它与旅行推销员问题不同——尽管这是相反的——有效地找到最高得分的组合，而不是最低的组合。在

如果是这样的话，那么在合理的时间内（对于任何大的数据集），你所能做的就是得到一个次优的分数，这个分数很接近，也许确实是最优的，但不可能证明它是次优的或最优的。在

一种简化方法是对你想填补的职位进行优先排序，并按优先顺序为每个职位获得最高分数-然而，与非优先职位列表相比，这甚至可能不是一个接近最佳的解决方案。在