设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法,对于给定的工作费用,为每一个人都分配1 件不同的工作,并使总费用达到最小。
时间: 2023-04-24 20:01:02 浏览: 196
算法设计工作分配
3星 · 编辑精心推荐
这是一个经典的任务分配问题,可以使用匈牙利算法来解决。具体步骤如下:
1. 初始化一个二维数组match,表示每个人分配的工作编号,初始值为-1。
2. 对于每个人i,从其可选的工作中选择费用最小的工作j,将match[i][j]赋值为1。
3. 如果有多个人选择了同一个工作,选择其中费用最小的人。
4. 对于每个人i,如果其没有被分配到工作,则从其可选的工作中选择费用最小的工作j,将match[i][j]赋值为1。
5. 重复步骤2-4,直到每个人都被分配到了工作。
6. 计算总费用,即所有分配的工作费用之和。
匈牙利算法的时间复杂度为O(n^3),可以在较短的时间内解决较大规模的问题。
阅读全文