最小工作分配问题：深度优先搜索算法求解

问题描述 设有n件工作分配给n个人，将工作i分配给第j个人费用为Cij，为每个人分配一件不同的工作，对于给定的工作费用，计算最佳工作分配方案，使得总费用达到最小。

输入格式 第一行有1个正整数(1<=n<=20).接下来的n行，每行n个数，第i行表示第i个人从事各项工作的费用

输出格式 共一行，即最小总费用

输入样例 3 4 2 5 2 3 6 3 4 5

输出样例 9

深度优先搜索算法求解

用深度优先搜索算法求解该问题，需要注意以下几点：

每个只能被分配一个工作，每个工作只能被分配给一个人，所以要用一个数组记录哪些工作已经被分配了，哪些人已经被分配了工作；
在搜索过程中，需要记录当前的总费用，以便判断是否达到最优解或者是否需要剪枝；
在搜索过程中，需要记录已经分配的工作数量，如果已经分配的工作数量达到n，说明所有工作都已经分配完毕，此时可以计算总费用并进行更新。同时，如果当前总费用已经大于已经得到的最小总费用，也可以进行剪枝。

参考代码

def dfs(current_cost, assigned_jobs, assigned_people, current_job, min_cost):
    if current_job == n:
        if current_cost < min_cost:
            min_cost = current_cost
        return min_cost
    for i in range(n):
        if assigned_jobs[i] == False and assigned_people[current_job] == False:
            assigned_jobs[i] = True
            assigned_people[current_job] = True
            min_cost = dfs(current_cost + costs[current_job][i], assigned_jobs, assigned_people, current_job + 1, min_cost)
            assigned_jobs[i] = False
            assigned_people[current_job] = False
    return min_cost

n = int(input())
costs = []
for i in range(n):
    costs.append(list(map(int, input().split())))

assigned_jobs = [False] * n
assigned_people = [False] * n
min_cost = float('inf')
min_cost = dfs(0, assigned_jobs, assigned_people, 0, min_cost)
print(min_cost)

算法解释

dfs(current_cost, assigned_jobs, assigned_people, current_job, min_cost) 函数实现深度优先搜索算法，参数分别表示当前费用，已分配工作数组，已分配人员数组，当前要分配的工作编号以及当前最小费用。
assigned_jobs 数组用于记录哪些工作已经被分配，assigned_people 数组用于记录哪些人已经被分配了工作。
current_job 表示当前要分配的工作编号，min_cost 表示当前得到的最小费用。
函数遍历所有未分配的工作，如果当前工作可以分配给当前人，则进行分配，并递归调用dfs 函数继续分配下一项工作。
如果所有工作都已经分配完毕，则计算当前总费用，并与当前最小费用进行比较，更新最小费用。
如果当前总费用已经大于当前最小费用，则进行剪枝，不再继续搜索。

代码示例

# 输入样例
3
4 2 5
2 3 6
3 4 5

# 代码输出
9

总结

本文介绍了使用深度优先搜索算法解决最小工作分配问题，并提供了详细的算法步骤和参考代码示例。深度优先搜索算法是一种常用的搜索算法，可以用于解决各种组合优化问题。在使用深度优先搜索算法解决问题时，需要注意剪枝操作，以提高算法效率。