#include <iostream>
using namespace std;
int best[100],x[100],c[100][100];
int min = 9999;
void swap(int &a,int &b)
{
int t = a;
a = b;
b = t;
}
void update(int n)
{
int sum = 0;
for(int i = 1; i <= n;i++)
sum += c[i][x[i]];
if(sum < min)
{
min = sum;
for(int i = 1;i <= n;i++)
best[i] = x[i];
}
}
void backtrack(int t,int n)
{
if(t > n)
update(n);
else
for(int i = t;i <= n;i++)
{
swap(x[t],x[i]);
backtrack(t+1,n);
swap(x[t],x[i]);
}
}
int main()
{
int n,i;
cout<<"输入n的值 :\n";
cin>>n;
for( i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
cin>>c[i][j];
for( i = 1;i <= n;i++)
x[i] = i;
backtrack(1,n);
for(i = 1;i <= n;i++)
cout<<"第"<<best[i]<<"号工作安排给第"<<i<<"个人\n";
cout<<"最小费用: "<<min;
cout<<"\n";
}
- 1
- 2
前往页