python - 使用 Python 的匈牙利算法约束

Question

我有工作和员工的数据框，每个员工可以完成每项工作的持续时间。我想使用匈牙利算法将每个工作分配给 1 个员工，每个员工只能分配 1 个工作。

这是数据：

    J1   J2   J3
E1  3    5    2
E2  7    3    9
E3  4    2    7
E4  2    7    5
E5  6    8    8

预期的结果是：

    J1   J2   J3
E1  0    0    1
E2  0    0    0
E3  0    1    0
E4  1    0    0
E5  0    0    0

然后打印出来：

Job   Employee
 1       4
 2       3
 3       1

谁能帮我解决这个问题？提前致谢！

score 2 · Accepted Answer

假设df输入数据框，您可以使用scipy.optimize.linear_sum_assignment：

from scipy.optimize import linear_sum_assignment
x,y = linear_sum_assignment(df)
out = pd.DataFrame({'Job': df.columns[y], 'Employee': df.index[x]})

输出：

  Job Employee
0  J3       E1
1  J2       E3
2  J1       E4

1 回答 1