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