回溯法——工作分配问题

工作分配问题是指将 n 个工作分配给 n 个人完成，每个人只能完成一个工作，每个工作需要一定的时间和费用。现在要求在满足每个工作都被分配的前提下，使得完成所有工作的总时间和费用最小。

这个问题可以使用回溯法解决。具体步骤如下：

1. 定义状态：使用一个 n 元数组 perm 存储工作的分配情况，其中 perm[i] 表示第 i 个工作被分配给了第 perm[i] 个人。

2. 定义限制条件：每个工作只能被分配一次，每个人只能完成一个工作。

3. 定义搜索顺序：采用深度优先搜索的方式，从第一个工作开始搜索。

4. 定义搜索策略：每次搜索时，枚举当前工作可以分配给哪些人，并计算分配后的总时间和费用。如果当前方案的时间和费用已经超过了之前搜索到的最优解，则剪枝返回。

5. 定义终止条件：所有工作都已经被分配，记录当前方案的时间和费用，并更新最优解。

最后，回溯法的时间复杂度是指数级的，因此只适用于工作数较小的情况。