匈牙利方法是为解决所谓“分配问题”,“指派问题”等数学问题的方法。这类问题的一般性叙述为:
有n个问题要分配给n个人去完成。第i个人完成第j项任务的成本为Cij。问:如何分配任务,能使总成本最小?
应用举例
引入变量Xij,Xij的取值表示:
Xij=1,指派第个人去完成第j项任务;
Xij=0,不指派第个人去完成第j项任务。
假如五个人完成五项任务,“成本矩阵”为:
12 7 9 7 9
8 9 6 6 6
7 17 12 14 9
15 14 6 6 10
4 10 7 10 9
解题过程:
每行减去其最小成本(即每行最小数):
(注意黑体)
5 0 2 0 2
2 3 0 0 0
0 10 5 7 2
9 8 0 0 4
0 6 3 6 5
最后一行与第三行的0重在第一列。把第三行,第五行减去这两行最小数2,第一列加上2。得:
7 0 2 0 2
4 3 0 0 0
0 8 3 5 0
11 8 0 0 4
0 4 1 4 3
即:X12=1,X23=1,X35=1,X44=1,X51=1。(其余Xij=0。)
#include<iostream.h>
#include"stdlib.h"
#include<ctime>
#include<stdio.h>
#define N 11
void main()
{
int juzhen[N][N];
int i,j;
double start,finish;
srand(1);
for(i=0;i<N;i++)
for(j=0;j<N;j++)
juzhen[i][j]=rand()%50;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout<<juzhen[i][j]<<" ";
cout<<endl;
}
cout<<"______________________"<<endl;
//先生成一个15*15的矩阵
/* 开始时间,结束时间 */
start=(double)clock();
int min=0,sum=0,k,l,t,m,n,max;
int count[N],same[N],compare[N];
for(i=0;i<N;i++)
{
min=juzhen[i][0];
l=0;
for(j=0;j<N;j++){
if(juzhen[i][j]<min)
{
min=juzhen[i][j];
l=j;
}
}
count[i]=l;
}
//找出每一行的最小值,并记住每一行的最小值的列数
for(i=0;i<N;i++)
cout<<count[i]<<" ";
cout<<endl;
//将每一行最小数的列数输出
for(i=0;i<N;i++)
{
t=count[i];
k=0;
for(j=0;j<N;j++)
{
if(t==count[j])
k++;
}
same[i]=k;
}
//检查每一行最小数在相同一列的次数
for(i=0;i<N;i++)
cout<<same[i]<<" ";
cout<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
if(i==count[j]) break;
if(j==N)
compare[i]=0;
else
compare[i]=1;
}
//检查哪列有最小值哪列没有,并标记。
for(i=0;i<N;i++)
cout<<compare[i]<<" ";
cout<<endl;
for(i=0;i<N;i++)
{
if(compare[i]==0)
{
for(j=0;j<N;j++)
{
if(same[j]>1)
{
max=0;
for(k=0;k<N;k++)
{
if(count[k]==count[j])
if(max<juzhen[k][count[k]])//找出同一列中各行最小数当中最大的数字,兵把他付给没有最小数的该列。
{
max=juzhen[k][count[k]];
m=k;
}
}
}
}
count[m]=i;
}
for(n=0;n<N;n++)
{
t=count[n];
k=0;
for(j=0;j<N;j++)
{
if(t==count[j])
k++;
}
same[n]=k;
}
for(n=0;n<N;n++)
{
for(j=0;j<N;j++)
if(n==count[j]) break;
if(j==N)
compare[n]=0;
else
compare[n]=1;
}
}
for(i=0;i<N;i++)
{
cout<<"第"<<i+1<<"行 第"<<count[i]+1<<"列为"<<juzhen[i][count[i]]<<endl;
sum=sum+juzhen[i][count[i]];
}
cout<<"最终值为:"<<sum<<endl;
finish = (double)clock();
printf("运行时间:%.4fms\n",(finish-start)/1000);
}