《matlab匈牙利算法》由会员分享，可在线阅读，更多相关《matlab匈牙利算法（4页珍藏版）》请在金锄头文库上搜索。
1、程序文件 fenpei.m function z,ans=fenpei(marix) %/%输入效率矩阵 marix 为方阵;%若效率矩阵中有M,则用一充分大的数代替；%输出z为最优解，ans为最优分配矩阵；%/a=marix；b=a；%确定矩阵维数s=length(a)；%确定矩阵行最小值，进行行减ml=min(a)；for i=1:sa(i,:)=a(i,:)-ml(i)；end%确定矩阵列最小值，进行列减mr=min(a)；for j=1:sa(:,j)=a(:,j)-mr(j)；end% start workingnum=0；while(num=s) %终止条件是“(0)”的个数与矩阵
2、的维数相同%index用以标记矩阵中的零元素，若a(i,j)=O，则index(i,j)=l,否则index(i,j)=O index=ones(s)； index=a&index； index=index；%flag 用以标记划线位， flag=0 表示未被划线，%flag=l 表示有划线过， flag=2 表示为两直线交点%ans 用以记录 a 中“(0)”的位置%循环后重新初始化 flag,ansflag = zeros(s)；ans = zeros(s)；%一次循环划线全过程，终止条件是所有的零元素均被直线覆盖，%即在 flag0 位,index=Owhile(sum(sum(inde
3、x)%按行找出“(0)”所在位置，并对“(0)”所在列划线，%即设置flag，同时修改index,将结果填入ansfor i=l:st=0；l=0；for j=l: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)”所在位置，并对“(0)”所在行划线%即设置flag，同时修改index,将结果填入ansfor j=1:st=0;r=0;for i=1:s if(flag(i,j)=0&index(i,j)=1)
4、r=r+1; t=i;endendif(r=1) flag(t,:)=flag(t,:)+1; index(t,:)=0; ans(t,j)=1;endendend %对 while(sum(sum(index)%处理过程%计数器：计算ans中1的个数，用num表示 num=sum(sum(ans);% 判断是否可以终止，若可以则跳出循环if(s=num)break;end%否则，进行下一步处理%确定未被划线的最小元素，用m表示 m=max(max(a);for i=1:sfor j=1:sif(flag(i,j)=0) if(a(i,j) a=37.732.938.83735.443.433
5、.142.234.741.833.328.538.930.433.629.226.429.628.531.100000; z,ans=fenpei(a)z =127.8000 ans =0000100010010001000000100注：求的ans是最小值！下题中要求的是最大喜好值，应把数值变成负数，0变成10。以此 求最小值。礼物【问题描述】G.Sha想到了该买些新年礼物送给朋友们。朋友们有各种各样的喜好。比如J.W.Zhang是RTS达人，应该送SC的战术杂志；而YGuan是“超级小宅男，一本正 经的礼物对他一律没用所以，G.Sha为礼物的事情伤透了脑筋商店有n件礼物出售，G.Sha有m
6、位朋友。G.Sha列出了每位朋友i对每件礼物j的喜好度aij (0aij100)o 请注意，喜好度aij可能等于0这代表着给某人买某件礼物是白花钱。所以选取礼物的方法有如下的约定： 1宁可不送某位朋友礼物，也绝不购买喜好度等于0的礼物。2每位朋友只收1件礼物。3礼物是不能复选的，即n件礼物中，每件礼物只有1份，只能送给1个朋友。在以上约定之下，请选择m件礼物，使所有朋友的喜好度总和尽可能大。【输入数据】输入文件 gift.in 包含 m+1 行。第1行，给出整数n, m,代表礼物和朋友的数量，满足mn。第2行第m+1行，每行n个整数，代表每位朋友i对礼物j的喜好度aij。【输出数据】输出文件g
7、ift.out包含m行。第1行第m行，每行一个整数，代表送给朋友i的礼物编号j。如果决定不给这位朋友买礼物，请输出0。 总喜好度由评测机计算，不必输出。【样例数据】gift.in4 38 1 9 112 2 27 15 0 5 0gift.out130说明：礼物1 给朋友1，礼物3给朋友2，总喜好度8+27=35。为了获得整体最优解，不给第3位朋友买礼物。【评分方法】如果你的程序的输出中存在不合法的情况(不是合法的m行整数、同一件礼物选多次、购买喜好度小于或等于0的礼物)， 则该测试点得 0分。否则设你的程序输出的方案能得到总喜好度S,得分按照以下规则计算：对于每个数据，都有一个评分参数 Ai。【数据规模】60%的数据中， m5, n20。100%的数据中， m100, n100。【提示】如果想拿部分分，请用点办法尽量拿得多一些，建议不要纯骗。 本题可以用匈牙利算法
