最小总费用：n作业优化分配策略

"回溯法解决n作业分配问题"是一个经典的优化问题，涉及在n个作业和n个人之间进行有效配对，使得每个人完成各自任务所需的总时间最小化。这个问题属于工作分配问题的范畴，其中每个作业i分配给工人j的成本（时间）由矩阵Cij表示。目标是找到一个解，使得总成本最低，同时确保每个工人只承担一项任务。 在给出的代码片段中，使用了回溯算法来求解此问题。回溯法是一种递归搜索策略，适用于具有大量可能解的问题空间。在这个场景中，算法通过以下步骤进行： 1. 初始化：首先，创建一个`WorkAssignment`类，其中包含作业时间矩阵`c`、当前作业调度数组`x`、最优解`bestx`、当前最优值`best`、作业数量`n`以及当前成本`cx`。定义一个友元函数`WorkAsmt`用于执行整个搜索过程。 2. 递归函数：`Backtrack`函数是核心，它在每一步检查剩余未分配的作业。当遍历到所有作业时，意味着找到了一个完整的解决方案，此时将当前的作业分配记录为最优解。如果当前成本小于最优成本，就尝试交换作业，然后递归地继续分配下一个作业。如果没有更优解，会回溯并尝试其他可能性。 3. 全局搜索：`WorkAsmt`函数负责调用`Backtrack`函数，初始时所有作业分配给对应的工人编号，然后设置上限值`ub`（这里假设为一个足够大的数），并开始搜索。搜索完成后，输出最小总费用以及每个作业分配给哪个工人的信息。 4. 内存管理：在搜索结束后，记得释放动态分配的内存，以防止内存泄漏。 总结来说，这段代码展示了如何运用回溯法来解决n作业分配问题，通过递归搜索所有可能的分配组合，找到成本最小且满足唯一作业分配的方案。这种方法对于处理大规模问题可能会效率较低，但适用于问题规模较小或者有明显局部最优性质的情况。