7-4 工作分配问题

工作分配问题是一种经典的优化问题，其目标是将n件工作分配给n个人，使得总费用最小。这里提供一种基于匈牙利算法的解决方案。

具体步骤如下：
1. 构建一个n×n的矩阵，其中第i行第j列的元素表示将工作i分配给第j个人所需的费用。
2. 初始化一个长度为n的数组match，用于记录每个人分配的工作编号。初始时，所有元素均为-1，表示所有人都未分配工作。
3. 对于每个人i，使用匈牙利算法寻找其可分配的工作。具体来说，从人i能够分配的所有工作中选择一个未被分配的工作j，如果将工作j分配给人i可以使得总费用减小，则将工作j分配给人i，并将match[i]设置为j。如果无法找到这样的工作，则说明人i无法分配工作，算法结束。
4. 最终，所有人都会被分配一个工作，且总费用最小。

下面是Python实现的代码示例：

def hungarian(cost):
    n = len(cost)
    match = [-1] * n
    for i in range(n):
        visited = [False] * n
        if find(i, cost, match, visited):
            continue
        else:
            break
    return match

def find(i, cost, match, visited):
    n = len(cost)
    for j in range(n):
        if cost[i][j] and not visited[j]:
            visited[j] = True
            if match[j] == -1 or find(match[j], cost, match, visited):
                match[j] = i
                return True
    return False