1. 实践题目 (工作分配问题)

2. 问题描述：设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小

3. 算法描述（包括解空间，画出测试样例的解空间树，剪枝（约束函数或限界函数）方法描述）

解空间：解空间为{x1,x2,x3,······,xn}，其中xi=1,2,3,4···,n，表示第i个人安排的工作号。

解空间树：测试样例工作数为3，解空间树如下：

剪枝方法：

　　约束条件:该工作是否已经被分配。

　　限界函数：当前工作花费是否大于最优花费，

代码：

#include
     
      using namespace std;#define N 1000int cost[N][N];int isC[N] = {
   0};int n;int scost;void Backstrack(int i, int c) {    if(c > scost) return;    if(i == n) {        if(c < scost) scost=c;        return;    }    for(int j=0;j
      
       >n;    for(int i=0;i
       
        >cost[i][j];        }    }    scost = N;    Backstrack(0,0);    cout<
       
      
     

 

　　心得体会（对本次实践收获及疑惑进行总结）

　　　　正确理解问题涉及的剪枝方法（限界函数，约束条件），回溯法就比较容易解决。不过在做题的时候一下子比较难确定好剪枝方法，或者说，确定之后不怎么会用代码实现。