一、实践题目
7-2 工作分配问题
题目描述：现在要将n份工作分配给n个人，其中每个人完成不同工作需要不同的花费，现在输入一个n表示n个人和n份工作，接着输入n行，每行n个数表示该人完成第i个工作所需要的花费。现在需要你求出为每一个人分配一件不同的工作，并使花费的最小值。
样例1：
//输入 3 10 2 3 2 3 4 3 4 5 //输出 9
题目分析：
该题需要每个人都必须分配到不同工作，题目中输入的数据可以用一个N*N的二维数组存取，其中a[i][j]表示第i个人完成第j个工作的花费是多少。我们可以遍历分配的所有情况，求得最小值。(即遍历解空间数，找到最小得花费值)。显然可以从一个人开始分配工作，每个人都有n种选择(1~n)，因此需要一个循环来遍历这n种选择，每次选择该工作后其他得人就不能重复选择，因此需要一个vis数组来标记每次已经访问过的工作，选择工作后记录选择该工作后的花费，递归进入下一层，为下一个人选择工作。直到>n时，表示最后一个人已经选择完工作，此时需要判断他是否比之前查找到的优答案还小，(之前查到的最优答案用一个全局变量ans记录)若是，则记录下来，若不是则忽略。直到最后则可以得到最优答案。
剪枝：
容易分析得知，在查找解空间时，存在许多不必要的查找。可以发现 当我们所记录的中间花费比当前的答案还大时(mid>ans)，则为不必要查找，因为继续查找下去的值可定不为最优值，所以可以将该部分通过剪枝去除。
解空间：
代码：
#include<iostream> #include<cstdio> using namespace std; int n; int a[101][101]; int vis[101]; int ans=0x3f3f3f,mids=0; void backtrack(int x) { if(x==n) //达到叶子结点，判断当前值是否优于答案 { if(ans>mids) ans=mids; return; } if(mids>ans) //剪枝 return; for(int i=0;i<n;i++) { if(!vis[i]) //选择未被选择过的工作 { mids+=a[x][i]; vis[i]=true; backtrack(x+1); mids-=a[x][i];//回溯 vis[i]=false; } } } int main() { cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j]; backtrack(0); cout<<ans<<endl; return 0; }
心得体会：
在本章的学习中明白了回溯法的具体使用和对题目解空间的构建，其中的回溯，通过限界函数减小访问
次数都能够较好的理解。主要不足在自己做题目时，很容易把剪枝的过程漏掉或者写错，导致代码超时或
者错误，还需多加练习。和队友的配合感觉也更加好了，能够一起学习进步，互相促进，希望能够更进一步。