组合太多

Question

嗨，我正在尝试生成所有可能的建筑工人组合。（让我解释一下我的情况）：

我在玩minecraft。在这个mod中，你有殖民者，他们可以被分配到建筑物中工作。这些工人拥有技能，并为他们分配了分数。（比如敏捷度：20，力量：5等等）如果指派一个技能与之相得益彰的殖民者，建筑物的工作表现会更好

所以我创建了一个所有工人和建筑物的数据库，希望优化哪些工人在哪些建筑物工作

buildings_dict = {1: ['Strength', 'Focus'],
                  2: ['Adaptability', 'Athletics'],
                  3: ['Knowledge', 'Dexterity'],
                  4: ['Adaptability', 'Knowledge'],
                  6: ['Stamina', 'Athletics'],
                  5: ['Athletics', 'Stamina'],
                  7: ['Focus', 'Agility'],
                  8: ['Dexterity', 'Creativity'],
                  9: ['Strength', 'Focus'],
                  10: ['Adaptability', 'Stamina'],
                  11: ['Agility', 'Adaptability'],
                  12: ['Mana', 'Knowledge'],
                  13: ['Strength', 'Stamina'],
                  14: ['Athletics', 'Strength'],
                  15: ['Creativity', 'Dexterity'],
                  16: ['Knowledge', 'Mana'],
                  17: ['Agility', 'Adaptability']}

workers_dict = {3: {'Mana': 30,
  'Focus': 1,
  'Agility': 3,
  'Stamina': 3,
  'Knowlege': 30,
  'Strenght': 8,
  'Athletics': 13,
  'Dexterity': 6,
  'Creativity': 10,
  'Adaptability': 10,
  'Intelligence': 10},
 4: {'Mana': 29,
  'Focus': 32,
  'Agility': 22,
  'Stamina': 28,
  'Knowlege': 21,
  'Strenght': 30,
  'Athletics': 20,
  'Dexterity': 31,
  'Creativity': 31,
  'Adaptability': 8,
  'Intelligence': 18},
 5: {'Mana': 13,
  'Focus': 1,
  'Agility': 9,
  'Stamina': 27,
  'Knowlege': 9,
  'Strenght': 13,
  'Athletics': 15,
  'Dexterity': 21,
  'Creativity': 16,
  'Adaptability': 13,
  'Intelligence': 28},
 6: {'Mana': 17,
  'Focus': 14,
  'Agility': 10,
  'Stamina': 17,
  'Knowlege': 13,
  'Strenght': 5,
  'Athletics': 10,
  'Dexterity': 15,
  'Creativity': 1,
  'Adaptability': 11,
  'Intelligence': 4},
 7: {'Mana': 1,
  'Focus': 8,
  'Agility': 6,
  'Stamina': 27,
  'Knowlege': 11,
  'Strenght': 17,
  'Athletics': 30,
  'Dexterity': 1,
  'Creativity': 5,
  'Adaptability': 11,
  'Intelligence': 5},
 8: {'Mana': 6,
  'Focus': 1,
  'Agility': 12,
  'Stamina': 30,
  'Knowlege': 20,
  'Strenght': 15,
  'Athletics': 30,
  'Dexterity': 9,
  'Creativity': 17,
  'Adaptability': 30,
  'Intelligence': 19},
 9: {'Mana': 5,
  'Focus': 7,
  'Agility': 19,
  'Stamina': 5,
  'Knowlege': 22,
  'Strenght': 18,
  'Athletics': 26,
  'Dexterity': 10,
  'Creativity': 24,
  'Adaptability': 20,
  'Intelligence': 22},
 10: {'Mana': 8,
  'Focus': 12,
  'Agility': 27,
  'Stamina': 3,
  'Knowlege': 17,
  'Strenght': 1,
  'Athletics': 5,
  'Dexterity': 9,
  'Creativity': 7,
  'Adaptability': 29,
  'Intelligence': 1},
 11: {'Mana': 1,
  'Focus': 4,
  'Agility': 5,
  'Stamina': 30,
  'Knowlege': 16,
  'Strenght': 11,
  'Athletics': 28,
  'Dexterity': 11,
  'Creativity': 5,
  'Adaptability': 12,
  'Intelligence': 4},
 12: {'Mana': 7,
  'Focus': 1,
  'Agility': 17,
  'Stamina': 25,
  'Knowlege': 23,
  'Strenght': 4,
  'Athletics': 8,
  'Dexterity': 26,
  'Creativity': 15,
  'Adaptability': 29,
  'Intelligence': 22},
 13: {'Mana': 2,
  'Focus': 1,
  'Agility': 5,
  'Stamina': 21,
  'Knowlege': 24,
  'Strenght': 18,
  'Athletics': 20,
  'Dexterity': 10,
  'Creativity': 12,
  'Adaptability': 30,
  'Intelligence': 5},
 14: {'Mana': 9,
  'Focus': 16,
  'Agility': 14,
  'Stamina': 25,
  'Knowlege': 14,
  'Strenght': 24,
  'Athletics': 30,
  'Dexterity': 9,
  'Creativity': 19,
  'Adaptability': 23,
  'Intelligence': 18},
 15: {'Mana': 23,
  'Focus': 15,
  'Agility': 5,
  'Stamina': 12,
  'Knowlege': 24,
  'Strenght': 12,
  'Athletics': 20,
  'Dexterity': 29,
  'Creativity': 5,
  'Adaptability': 19,
  'Intelligence': 12},
 17: {'Mana': 21,
  'Focus': 23,
  'Agility': 30,
  'Stamina': 18,
  'Knowlege': 27,
  'Strenght': 7,
  'Athletics': 30,
  'Dexterity': 10,
  'Creativity': 5,
  'Adaptability': 22,
  'Intelligence': 18},
 18: {'Mana': 11,
  'Focus': 11,
  'Agility': 4,
  'Stamina': 7,
  'Knowlege': 28,
  'Strenght': 11,
  'Athletics': 20,
  'Dexterity': 28,
  'Creativity': 13,
  'Adaptability': 12,
  'Intelligence': 30},
 19: {'Mana': 11,
  'Focus': 11,
  'Agility': 4,
  'Stamina': 7,
  'Knowlege': 28,
  'Strenght': 11,
  'Athletics': 20,
  'Dexterity': 28,
  'Creativity': 13,
  'Adaptability': 12,
  'Intelligence': 30},
 20: {'Mana': 15,
  'Focus': 20,
  'Agility': 28,
  'Stamina': 22,
  'Knowlege': 18,
  'Strenght': 15,
  'Athletics': 23,
  'Dexterity': 19,
  'Creativity': 20,
  'Adaptability': 27,
  'Intelligence': 20},
 21: {'Mana': 30,
  'Focus': 7,
  'Agility': 9,
  'Stamina': 7,
  'Knowlege': 30,
  'Strenght': 3,
  'Athletics': 6,
  'Dexterity': 17,
  'Creativity': 4,
  'Adaptability': 11,
  'Intelligence': 28},
 22: {'Mana': 9,
  'Focus': 10,
  'Agility': 28,
  'Stamina': 26,
  'Knowlege': 1,
  'Strenght': 8,
  'Athletics': 5,
  'Dexterity': 26,
  'Creativity': 1,
  'Adaptability': 14,
  'Intelligence': 16},
 23: {'Mana': 4,
  'Focus': 14,
  'Agility': 19,
  'Stamina': 5,
  'Knowledge': 21,
  'Strength': 25,
  'Athletics': 12,
  'Dexterity': 23,
  'Creativity': 26,
  'Adaptability': 21,
  'Intelligence': 22},
 24: {'Mana': 1,
  'Focus': 1,
  'Agility': 18,
  'Stamina': 24,
  'Knowledge': 25,
  'Strength': 20,
  'Athletics': 9,
  'Dexterity': 14,
  'Creativity': 19,
  'Adaptability': 30,
  'Intelligence': 7},
 25: {'Mana': 12,
  'Focus': 13,
  'Agility': 21,
  'Stamina': 23,
  'Knowledge': 11,
  'Strength': 16,
  'Athletics': 18,
  'Dexterity': 24,
  'Creativity': 1,
  'Adaptability': 20,
  'Intelligence': 1},
 26: {'Mana': 10,
  'Focus': 14,
  'Agility': 12,
  'Stamina': 27,
  'Knowledge': 17,
  'Strength': 24,
  'Athletics': 23,
  'Dexterity': 21,
  'Creativity': 5,
  'Adaptability': 5,
  'Intelligence': 28},
 27: {'Mana': 11,
  'Focus': 23,
  'Agility': 21,
  'Stamina': 12,
  'Knowledge': 15,
  'Strength': 24,
  'Athletics': 17,
  'Dexterity': 12,
  'Creativity': 1,
  'Adaptability': 11,
  'Intelligence': 9},
 28: {'Mana': 7,
  'Focus': 21,
  'Agility': 22,
  'Stamina': 21,
  'Knowledge': 14,
  'Strength': 15,
  'Athletics': 9,
  'Dexterity': 16,
  'Creativity': 2,
  'Adaptability': 11,
  'Intelligence': 5},
 29: {'Mana': 12,
  'Focus': 25,
  'Agility': 29,
  'Stamina': 6,
  'Knowledge': 7,
  'Strength': 10,
  'Athletics': 14,
  'Dexterity': 15,
  'Creativity': 6,
  'Adaptability': 13,
  'Intelligence': 29},
 30: {'Mana': 21,
  'Focus': 17,
  'Agility': 8,
  'Stamina': 21,
  'Knowledge': 22,
  'Strength': 22,
  'Athletics': 26,
  'Dexterity': 13,
  'Creativity': 15,
  'Adaptability': 24,
  'Intelligence': 13}}

很抱歉代码块太长，是的，我意识到ID不一定正确（我想让它重现）

因此，我使用itertools.permutations让所有工人组合到建筑物中：

import itertools
workers_ls = list(workers_dict.keys())
combinations = list(itertools.permutations(workers_ls, len(buildings_dict))

（我计划在之后为组合打分）

显然，这辆车从来没有跑完，因为它大约是27辆1×10²⁸. 我想知道我的问题是否有另一种解决方案，或者是一种不用经过每种组合就能确定最佳解决方案的方法。（我愿意使用其他编码语言）

谢谢

Answer 1

我假设你想使总产量最大化。例如，当未分配工人时，总产量为零（或不依赖于工人分配的某个常数）。如果将工人与Agility2和Focus3与属性为[Agility, Focus]的建筑配对，则将2+3=5添加到总产量中

像这样的问题通常用线性规划来解决。我将使用pulp来帮助制定线性规划问题。我还建议查看Julia包JuMP

计算总产量的实际规则可能更复杂。如果（1）可以定义生产矩阵的一些模拟值，（2）总产量可以表示为（工人、建筑）对生产的总和，则仍然可以使用线性规划

这里有两种方法来解决这个问题。第一个允许每个建筑有多个工人，第二个不允许

设置

import pandas as pd
import numpy as np
# !pip install pulp
import pulp

df_buildings = pd.DataFrame(buildings_dict).T
df_workers = pd.DataFrame(workers_dict).T

# there are a few typos, e.g. Strenght vs. Strength and Knowlege vs. Knowledge
# let's fix this first
df_workers.Knowledge.fillna(df_workers.Knowlege, inplace=True)
df_workers.Strength.fillna(df_workers.Strenght, inplace=True)
del df_workers["Strenght"], df_workers["Knowlege"]

# fixing some notation
workers = df_workers.index.tolist() # list of workers
buildings =  df_buildings.index.tolist() # list of building

# next, we define production matrix
# production[i,j] will contain the productivity of 
# worker i when assigned to building j
# you could vectorize this step, though it seems fast enough here
production = pd.DataFrame(index=workers, columns=buildings)
for i in df_workers.index:
  for j in df_buildings.index:
    production.loc[i, j] = df_workers.loc[i, df_buildings.loc[j]].sum()

print(production.head())
#    1   2   3   4   6   5   7   8   9   10  11  12  13  14  15  16  17
# 3   9  23  36  40  16  16   4  16   9  13  13  60  11  21  16  60  13
# 4  62  28  52  29  48  48  54  62  62  36  30  50  58  50  62  50  30
# 5  14  28  30  22  42  42  10  37  14  40  22  22  40  28  37  22  22
# 6  19  21  28  24  27  27  24  16  19  28  21  30  22  15  16  30  21
# 7  25  41  12  22  57  57  14   6  25  38  17  12  44  47   6  12  17

允许每个建筑有多个工人

prob = pulp.LpProblem("MineColoniesProblem", pulp.LpMaximize)

# in the solved problem, assignment[i,j] == 1 whenever i is assigned to j
assignment = pulp.LpVariable.dicts("Assignment", (workers, buildings), cat="Binary")

# our objective is to maximize the sum of production
prob += sum(assignment[i][j] * production.loc[i,j]
            for i in workers for j in buildings)

# each worker can be assigned to at most one building:
for i in workers:
  prob += sum(assignment[i][j] for j in buildings) <= 1

prob.solve()
# make sure that we got an optimal solution
assert prob.status == 1

# generically, we get an integer solution
assignment_dict = {i: j for i in workers for j in buildings
                   if assignment[i][j].varValue == 1}
print(f"Total production is {prob.objective.value()}") # 1401

# here is the the solution
# assignment_dict_saved = {3: 12, 4: 1, 5: 5, 6: 16, 7: 5, 8: 6, 9: 2, 10: 17, 11: 6, 12: 10, 13: 4, 14: 6, 15: 3, 17: 7, 18: 3, 19: 3, 20: 11, 21: 12, 22: 17, 23: 15, 24: 4, 25: 10, 26: 13, 27: 9, 28: 7, 29: 7, 30: 2}

每栋建筑最多一名工人

prob = pulp.LpProblem("MineColoniesProblem", pulp.LpMaximize)

# in the solved problem, assignment[i,j] == 1 whenever i is assigned to j
assignment = pulp.LpVariable.dicts("Assignment", (workers, buildings), cat="Binary")

# our objective is to maximize the sum of production
prob += sum(assignment[i][j] * production.loc[i,j]
            for i in workers for j in buildings)

# each worker can be assigned to at most one building:
for i in workers:
  prob += sum(assignment[i][j] for j in buildings) <= 1

# each building has at most one worker
for j in buildings:
  prob += sum(assignment[i][j] for i in workers) <= 1

prob.solve()
# make sure that we got an optimal solution
assert prob.status == 1

# generically, we get an integer solution
assignment_dict = {i: j for i in workers for j in buildings
                   if assignment[i][j].varValue == 1}
# assignment_dict_saved = {3: 16, 4: 9, 7: 5, 8: 2, 10: 11, 11: 6, 12: 10, 14: 14, 18: 3, 19: 8, 20: 17, 21: 12, 23: 15, 24: 4, 26: 13, 27: 1, 29: 7}
print(f"Total production is {prob.objective.value()}") # 929

---

我们可以看到，当我们允许每个建筑有多个工人时，总产量更高。这是意料之中的，因为最大化问题具有较少的约束

我们还可以将优化生产与工人随机分配到建筑物时的生产进行比较。垂直线对应于最佳生产。看起来我们做得很好