设立一、问题描述：件工作分配给n个人。 将工作I分配给j人所需的费用是。 试着设计算法，给每个人分配一个不同的工作，使总费用最小。

第输入格式：行有一个正整数n ()。 接下来的n行，每行n个数表示费用。

——输入样例：

3

10 2 3

2 3 4

3 4 5

——输出样例：

9

二、算法解析：解决这个问题的总体思想是利用回溯法的思想。 将可能出现的所有解逻辑地构建成“树”，并利用一些条件为该树“剪枝”。 (排除一些解的情况)； 可以解得更快！

准备工作：

横轴表示第几个工作，纵轴使用表示第几个工人的二维数组money记录相应的费用。

由于所有工作与所有工人之间存在一对一的关系，因此使用一维数组work表示已经分配了工作的工人。 (0表示未分配，1表示已经分配。 ）

使用全局变量minPay记录最小的总费用。 本地变量nowPay表示计算中的本地累计费用。

使用变量t表示当前已解决问题的深度。 (即被分配到哪个工作) )。

具体情形：

):nowPay大于最小pay； 表示目前累计的费用大于已有的最小值，没有继续的意义，只会导致费用进一步加大。

情况) tn； 指示当前分配进度的深度未达到“叶节点”。 也就是说，所有的工作都还没有分配。 继续相应的分配工作。

):t==n； 指示当前分配进展的深度已达到“叶节点()，即所有工作均已分配)； 此时，比较nowPay和minPay的值，minPay取其中的最小值。

三、代码实现： import java.util.Scanner； public class test { publicstaticvoidmain (string [ ] args ) scanners=newscanner ) system.in )； int n=s.nextInt (； //接收人数int[][] money=new int[n 1][n 1]； //用于接收对应费用的for(intI=1； i=n； I ) for(intj=1； j=n； j ) money[i][j]=s.nextInt (； s.close (； //接收完成int[]work=new int[n 1]； //用来表示被分配的工作的人是什么； 0表示未分配，1表示分配了searchminpay (0，0，n，money，work )。 System.out.println (‘最小费用为’ minPay ‘ )； }public static int minPay=10000； //为了记录最小费用/* * t表示深度级别，* nowPay表示当前累计费用* n和money，work为辅助数据。 */publicstaticvoidsearchminpay (intt，int nowPay，int n，int[][] money，int[]work ) if ) nowpayminpay||TN ) ) i=n； I ) if(work[I]==0) /找到一个未被分配工作的人nowPay=money[t 1][i]； work[i]=1； searchminpay(t1，nowPay，n，money，work )； nowPay-=money[t 1][i]； //恢复数据，便于追溯。 work[i]=0； }}if(t==n ) ) /到了叶节点，表示工作已分配到if ) nowpayminpay )

{//保留最佳的数据minPay = nowPay;}else {//舍弃return;}}}}

四、优化思路：

①对于minPay的初始值设置进行优化：

在上述代码中，minPay的初值被设置为一个足够大的数，这样使得在实际使用的过程中，minPay是在出现第一个可行解时取其值作为自己的值再利用 if(nowPay>minPay||t>n) 来筛选不用再继续下去的分配；为了提高其筛选效率，我们可以通过将minPay的初值直接赋予一个可行解再进行分配工作，这样 if(nowPay>minPay||t>n)  语句就不用等到出现第一个可行解再起作用了；那么我们如何在不通过运算就可以找到一个可行解呢？

显而易见，按照二维数组 money 的对角线进行工作分配就是一个可行解！

②对于分配方式的筛选机制进行了优化：

对于分配的筛选，在上述的代码中我们仅仅依靠的是 if(nowPay>minPay||t>n)  语句来过滤；其实还有一种更为巧妙的筛选机制！

我们将money数组的每一行数据的最小值存储在一个一维数组array中（即完成某一工作的最小花费），当分配到某一个工作时，我们将 nowPay 累计加上剩余未分配工作对应行在一维数组array中存储的最小值，如果得到的 nowPay 值大于 minPay；则说明这条分配线路不会得到更优的解。

在这里你可能会疑惑将money每一行的最小值存入一维数组array中；可能不同工作的最小花费是属于同一个工人，这样不就是违背了我们题干中的要求了吗？

这里的使用并没有错，因为我们设置一维数组array的目的仅仅利用它的值，并不涉及逻辑概念，因为你无论怎么安排工作，最终累加的花费是是大于array中对应元素的累加和。

——其实此处对于一位数组array的使用，还有优化的空间！

将一位数组array初始化为二维数组money每一行元素的最小值（注意下标要对应上）；然后令array[i]+=array[i+1]（倒序，i 从 n 一直取到 1）；这样nowPay在累加剩余未分配工作对应行在一维数组array中存储的最小值时，直接加上对应的array[i]元素就可以了！

五：优化之后的代码：

为了让优化的效果可视化，我加了一个静态变量count用于记录调用函数的次数，在searchMinPay函数中加上了以下语句：

count++;System.out.println(“第”+count+”次：”+”nowPay：”+nowPay+” “+”minPay：”+minPay);

原地代码中的

if(nowPay>minPay||t>n)

也改为相应的 

if((nowPay+array[t])>minPay||t>n) import java.util.Scanner;public class test {public static void main(String[] args) {Scanner s = new Scanner(System.in);int n = s.nextInt();//用于接收人数int[][] money = new int[n+1][n+1];//用于接收对应的费用for(int i = 1;i<=n;i++)for(int j = 1;j<=n;j++)money[i][j] = s.nextInt();s.close();//接收完毕int[]work = new int[n+1];//用于表示已分配的工作的人有哪些；0表示未分配，1表示已分配minPay = 0;//初始化minPayfor(int i=1;i<=n;i++) minPay+=money[i][i];for(int i=1;i<=n;i++) {//初始化array数组int minvalue = money[i][1];for(int j=1;j<=n;j++) {//找出每一行的最小值if(money[i][j]<minvalue)minvalue = money[i][j];}array[i] = minvalue;}for(int i = n-1;i>=1;i–)array[i]+=array[i+1];searchMinPay(0, 0, n, money,work);System.out.println(“最小费用为：”+minPay);}public static int minPay = 10000;//用于记录最小的费用public static int[] array = new int[30];//用于记录二维数组money每一行数据的最小值/* * t表示深度层级， * nowPay表示当前的累计费用 * n和money,work为辅助数据。 */public static int count = 0;//用于计数public static void searchMinPay(int t,int nowPay,int n,int[][] money,int[]work) {count++;System.out.println(“第”+count+”次：”+”nowPay：”+nowPay+” “+”minPay：”+minPay);if((nowPay+array[t])>minPay||t>n) {//继续下去已经没有意义return;}if(t<n) {//工作尚未分配完，继续分配for(int i=1;i<=n;i++) {if(work[i]==0) {//找到一个未分配工作的人nowPay+=money[t+1][i];work[i] = 1;searchMinPay(t+1, nowPay, n, money,work);nowPay-=money[t+1][i];//恢复数据， 便于回溯work[i] = 0;}}}if(t==n) {//表示到了叶子结点，工作已经分配完了if(nowPay<minPay) {//保留最佳的数据minPay = nowPay;}else {//舍弃return;}}}} 右边为优化前，左边为优化后

Ending… ….