Доброво времени суток! помогите решить задачу о назначениях (венгкрский алгоритм) на pascal или delphi...
Задача:
Пять человек должны выполнить четыре работы, причём каждый из работников с разной производительностью может выполнить любую из этих работ. Предусматривается, что каждый работник в состоянии сделать только одну работу.
Производительность работников задана матрицей:
3 4 2 2 1
4 5 3 1 3
4 3 1 1 1
3 1 2 2 2
0 0 0 0 0
Распределить людей так, чтобы выполнить её с максимальной производительностью.
В принцмпе решение с соблюдением алготма не обязательно...
Я делал на pascal (с реализацией метода) и моя работа остановилась на выводе редуцированной матрице.
Текст программы:
Program m;
Var
t,st1,st2,st3,st4,st5,sb1,sb2,sb3,sb4,sb5,minsrsb,imax,jmax,i,j,max,sum:integer;
a:array[1..5,1..5] of integer; //ishodnaj matrica
b:array[1..5] of integer; //massiv summi nullei v strokah
c:array[1..5] of integer; //massiv summi nullei v stolbcah
Begin
//znacenie elementov ishodnoi matrici
a[1,1]:=3; a[1,2]:=4; a[1,3]:=2; a[1,4]:=2; a[1,5]:=1;
a[2,1]:=4; a[2,2]:=5; a[2,3]:=3; a[2,4]:=1; a[2,5]:=3;
a[3,1]:=4; a[3,2]:=3; a[3,3]:=1; a[3,4]:=1; a[3,5]:=1;
a[4,1]:=3; a[4,2]:=1; a[4,3]:=2; a[4,4]:=2; a[4,5]:=2;
a[5,1]:=0; a[5,2]:=0; a[5,3]:=0; a[5,4]:=0; a[5,5]:=0;
//ishodno-uslovnoe kolicestvo nullei po stolbcam v reducirovannoi matrice
b[1]:=0; b[2]:=0; b[3]:=0; b[4]:=0; b[5]:=0;
//ishodno-uslovnoe kolicestvo nullei po strokam v reducirovannoi matrice
c[1]:=0; c[2]:=0; c[3]:=0; c[4]:=0; c[5]:=0;
begin //vivod ishodnoi matrici
writeln('Ishodnai matrica');
for i:=1 to 5 do
begin
for j:=1 to 5 do
Write(a[i,j]);
writeln;
end;
end;
begin //poisk i vivod maximalnogo elemeta v matrice
imax:=1; jmax:=1;
for i:=1 to 5 do
for j:=1 to 5 do
if a[imax,jmax]<a[i,j]
then begin
imax:=i; jmax:=j;
end;
writeln;
writeln('maximalnii element: ',a[imax,jmax]);
end;
begin //umnojenie elementov matrici na (-1) i slojenie s maximalnim elementom
for i:=1 to 5 do
for j:=1 to 5 do
a[i,j]:=a[i,j]*(-1)+a[imax,jmax];
begin //vivod poluchennoi matrici
writeln;
writeln('poluchennaj matrica posle preobrazovanij reshenij zadachi na maximum:');
for i:=1 to 5 do
begin
for j:=1 to 5 do
Write(a[i,j]);
writeln;
end;
end;
end;
begin //opredelenie minimalnih elementov strok
writeln();
for i:=1 to 5 do
begin
minsrsb:=a[i,1];
for j:=1 to 5 do
if minsrsb>a[i,j]then
minsrsb:=a[i,j];
begin
for j:=1 to 5 do
a[i,j]:=a[i,j]-minsrsb;
end;
writeln('minimalnii element stroki ',i,'= ',minsrsb);
end;
end;
begin //вывод редуцированной матрицы по строкам
writeln();
writeln('матрица редуцированная по строкам');
for i:=1 to 5 do
begin
for j:=1 to 5 do
Write(a[i,j]);
writeln;
end;
end;
begin //определение минимальных элементов столбцов
writeln();
for j:=1 to 5 do
begin
minsrsb:=a[j,1];
for i:=1 to 5 do
if minsrsb>a[i,j]then
minsrsb:=a[i,j];
begin
for i:=1 to 5 do
a[i,j]:=a[i,j]-minsrsb;
end;
writeln('миниальный элемент столбца ',j,'= ',minsrsb);
end;
end;
begin //вывод редуцированной матрицы по строкам
writeln();
writeln('матрица редуцированная по столбцам');
for i:=1 to 5 do
begin
for j:=1 to 5 do
Write(a[i,j]);
writeln;
end;
end;
begin //определение количества нулей в строках
writeln();
for i:=1 to 5 do
begin
for j:=1 to 5 do
if a[i,j]=0 then
b:=b+1;
writeln('количество нулей в строке'#32,i,'-',#32,b);
end;
end;
begin //определение количества нулей в стобцах
writeln();
for j:=1 to 5 do
begin
for i:=1 to 5 do
if a[i,j]=0 then
c[j]:=c[j]+1;
writeln('количество нулей в столбце'#32,j,'-',#32,c[j]);
end;
end;
begin
end;
End.
Большое спасибо за любую помощь...
PS схожу с ума от того, что не могу найти как это делеть
извенити за коментарии то на русском, то на латинеце