matlab匈牙利算法

1、程序文件 fenpei.m function z,ans=fenpei(marix) %/%輸入效率矩陣marix 為方陣 ;%若效率矩陣中有M, 則用一充分大的數(shù)代替 ;%輸出 z 為最優(yōu)解， ans 為 最優(yōu)分配矩陣；%/a=marix;b=a;%確定矩陣維數(shù)s=length(a);%確定矩陣行最小值，進(jìn)行行減ml=min(a');for i=1:sa(i,:)=a(i,:)-ml(i);end%確定矩陣列最小值，進(jìn)行列減mr=min(a);for j=1:sa(:,j)=a(:,j)-mr(j);end% start workingnum=0;while(num=s)% 終止條件

2、是“ ( 0)”的個(gè)數(shù)與矩陣的維數(shù)相同%index 用以標(biāo)記矩陣中的零元素，若 a(i,j)=0 ，則 index(i,j)=1, 否則 index(i,j)=0 index=ones(s);index=a&index;index=index;%flag 用以標(biāo)記劃線位， flag=0 表示未被劃線，%flag=1 表示有劃線過， flag=2 表示為兩直線交點(diǎn)%ans 用以記錄 a 中“(0)”的位置%循環(huán)后重新初始化flag,ansflag = zeros(s);ans = zeros(s);%一次循環(huán)劃線全過程，終止條件是所有的零元素均被直線覆蓋，%即在 flag>0 位

3、,index=0while(sum(sum(index)%按行找出“(0)”所在位置，并對(duì)“ ( 0)”所在列劃線，%即設(shè)置flag,同時(shí)修改index,將結(jié)果填入ansfor i=1:st=0;l=0;for j=1:sif(flag(i,j)=0&&index(i,j)=1)l=l+1;t=j;endendif(l=1) flag(:,t)=flag(:,t)+1; index(:,t)=0; ans(i,t)=1;endend %按列找出“(0)”所在位置，并對(duì)“ ( 0)”所在行劃線，%即設(shè)置flag,同時(shí)修改index,將結(jié)果填入ansfor j=1:st=0;r=0

4、;for i=1:s if(flag(i,j)=0&&index(i,j)=1) r=r+1; t=i;endendif(r=1) flag(t,:)=flag(t,:)+1; index(t,:)=0; ans(t,j)=1;endendend %對(duì) while(sum(sum(index)%處理過程%計(jì)數(shù)器：計(jì)算ans中1的個(gè)數(shù)，用num表示 num=sum(sum(ans);% 判斷是否可以終止，若可以則跳出循環(huán)if(s=num)break;end%否則，進(jìn)行下一步處理 %確定未被劃線的最小元素，用 m 表示m=max(max(a);for i=1:sfor j=1:si

5、f(flag(i,j)=0) if(a(i,j)<m)m=a(i,j);endendendend%未被劃線，即flag=0處減去m;線交點(diǎn)，即flag=2處加上m for i=1:sfor j=1:sif(flag(i,j)=0)a(i,j)=a(i,j)-m;endif(flag(i,j)=2)a(i,j)=a(i,j)+m;endendendend %對(duì) while(num=s)%計(jì)算最優(yōu)( min )值 zm=ans.*b;z=0;z=sum(sum(zm);/ /運(yùn)行實(shí)例：>> a=37.732.938.83735.443.433.142.234.741.833.32

6、8.538.930.433.629.226.429.628.531.10 0000;>> z,ans=fenpei(a)z =127.8000 ans =100000 0 0 00 0 0 10 1 0 01 0 0 00 變成 10。以此0 0 1 0注：求的 ans 是最小值！下題中要求的是最大喜好值，應(yīng)把數(shù)值變成負(fù)數(shù)， 求最小值。禮物【問題描述】G.Sha 想到了該買些新年禮物送給朋友們。朋友們有各種各樣的喜好。比如 J.W.Zhang是RTS達(dá)人，應(yīng)該送SC的戰(zhàn)術(shù)雜志；而Y.Guan是超級(jí)小宅男”，一本正 經(jīng)的禮物對(duì)他一律沒用 所以，G.Sha為禮物的事情傷透了腦筋 商店有

7、n件禮物出售，G.Sha有m位朋友。G.Sha列出了每位朋友i對(duì)每件禮物j的喜好度aij (0 <aij <100)請(qǐng)注意，喜好度aij可能等于0,這代表著給某人買某件禮物是白花錢。 所以選取禮物的方法有如下的約定：1 寧可不送某位朋友禮物，也絕不購買喜好度等于 0 的禮物。2每位朋友只收 1 件禮物。3禮物是不能復(fù)選的，即 n 件禮物中，每件禮物只有 1 份，只能送給 1 個(gè)朋友。 在以上約定之下，請(qǐng)選擇 m 件禮物，使所有朋友的喜好度總和盡可能大?！据斎霐?shù)據(jù)】輸入文件 gift.in 包含 m+1 行。第1行，給出整數(shù)n, m，代表禮物和朋友的數(shù)量，滿足 n<n。第2行第

8、m+1行，每行n個(gè)整數(shù)，代表每位朋友i對(duì)禮物j的喜好度aij?！据敵鰯?shù)據(jù)】輸出文件 gift.out 包含 m 行。第1行第m行，每行一個(gè)整數(shù)，代表送給朋友i的禮物編號(hào)j。如果決定不給這位朋友買禮物，請(qǐng)輸出 0。 總喜好度由評(píng)測機(jī)計(jì)算，不必輸出?！緲永龜?shù)據(jù)】gift.in4 38 1 9 112 2 27 15 0 5 0gift.out130說明：禮物 1 給朋友 1，禮物 3給朋友 2，總喜好度 8+27=35 。為了獲得整體最優(yōu)解，不給第 3 位朋友買禮物?！驹u(píng)分方法】如果你的程序的輸出中存在不合法的情況 (不是合法的 m 行整數(shù)、同一件禮物選多次、購買喜好度小于或等于 0 的禮物)， 則該測試點(diǎn)得 0分。否則設(shè)你的程序輸出的方案能得到總喜好度 S ，得分按照以下