回溯法解决工作分派问题

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

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

输出: