回溯法解决工作分派问题

本文主要是介绍回溯法解决工作分派问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解决这个问题的关键有两个:

1.t数组用来在回溯过程暂时存储工作分配关系

2.ans数组用来保存最终答案

3."恢复现场"操作

4.一维数组st,表示该工作是否已经被选

5.solve第k层递归表示第k个人,for循环罗列的是工作.这样,比k表示工作,for循环枚举人更加符合我们的直觉和生活常识

#include<iostream>
#include<limits.h>
using namespace std;
const int N=100;
int C[N][N];
int t[N][N];//t数组和ans数组是关系矩阵,若其值为1,表示第k个人选择第i份工作 
int ans[N][N];//t数组用来在回溯过程进行暂时存储,ans用来保存答案 
bool st[N];//st数组只需一维,一一对应工作 
int n,m;
int MIN=INT_MAX;
int cost; 
/*
5
1 2 3 4 5
5 4 3 2 1
12 11 13 14 15
10 9 6 8 7
9 6 15 5 8
*/
/*
5
1 2 3 4 5
5 4 3 2 1
15 14 13 12 11
10 9 6 8 7
9 6 15 5 8
*/
void solve(int k)//k代表人,是C数组中的行 
{for(int i=1;i<=n;i++)//i代表工作 ,是C数组中的列 {if(!st[i]){cost+=C[k][i];t[k][i]=1;st[i]=true;if(k!=n){solve(k+1);cost-=C[k][i];t[k][i]=0;st[i]=false;}else if(k==n){if(cost<MIN){MIN=cost;for(int p=1;p<=n;p++)for(int q=1;q<=n;q++)ans[p][q]=t[p][q];//					printf("最小成本总和为:%d\n",MIN);
//					printf("各个人的工作及其成本为:\n");
//					for(int p=1;p<=n;p++)
//						for(int q=1;q<=n;q++)
//							if(t[p][q]!=0)
//								printf("第%d个人找到了第%d份工作,成本为:%d\n",p,q,C[p][q]);}cost-=C[k][i];t[k][i]=0;st[i]=false;}}}
}
int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&C[i][j]);solve(1);printf("最小成本总和为:%d\n",MIN);printf("各个人的工作及其成本为:\n");for(int p=1;p<=n;p++)for(int q=1;q<=n;q++)if(ans[p][q]!=0)printf("第%d个人找到了第%d份工作,成本为:%d\n",p,q,C[p][q]);return 0;
}

输入:

5
1 2 3 4 5
5 4 3 2 1
15 14 13 12 11
10 9 6 8 7
9 6 15 5 8

输出: