问题描述：
设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j] 。试设计一个算法，计算最佳工作分配方案，为每一个人都分配1 件不同的工作，并使总费用达到最小。
数据输入 ：
第一行一个正整数n(1<=n<=20),接下来的n 行，每行n 个数，表示工作费用 。
结果输出:
输出有m行，每行输出最小总费用。
输入样例：
5
50 43 1 58 60
87 22 5 62 71
62 98 97 27 38
56 57 96 73 71
92 36 43 27 95
输出样例：
144
用回溯法求解，这就是在全排列中找出费用最小的
//工作分配问题
/*
3
10 2 3
2 3 4
3 4 5
*/
#include <iostream>
#include <algorithm>
using namespace std;
int table[21][21],n,best,r[21];
int compute(int k)
{
int temp=0,i;
for(i=1;i<=k;i++)
temp+=table[i][r[i]];
return temp;
}
void search(int k)
{
if(k==n)
{
int temp=compute(n);
if(temp<best)
best=temp;
return;
}
for(int i=k;i<=n;i++)
{
swap(r[i],r[k]);
if(compute(k) < best)
search(k+1);
swap(r[i],r[k]);
}
}
int main()
{
int i,j;
while(cin>>n,n)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>table[i][j];
for(i=1;i<=n;i++)
r[i]=i;
best=INT_MAX;
search(1);
cout<<best<<endl;
}
return 0;
}
posted on 2012-10-24 22:24
大大木马 阅读(8191)
评论(1) 编辑 收藏 引用