运动员最佳匹配问题(详解)
创始人
2024-06-01 12:15:23
0次

一、问题描述

羽毛球队有男女运动员各n人。给定2个n×n矩阵P和Q。
P[i][j]是男运动员i的女运动员j配对组成混合双打的男运动员竞赛优势;Q[i][j]是女运动员i和男运动员j配对的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响,P[i][j]不一定等于Q[i][j]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]×Q[i][j]。
设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。
输入样例:(第一行是男队员(或女队员)的个数,第二、三、四行是男运动员i 和女运动员j配对组成混合双打的男运动员竞赛优势,第五、六、七行是女运动员i和男运动员j配合的女运动员竞赛优势)
3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1
输出样例:(第一行是竞赛优势的最大和)
52

二、算法思路

固定男运动员,对女运动员进行一次全排列,并求出每位男运动员能匹配到的最大优势值。本题共有n!种配对情况。

固定1号男运动员,让所有的n个女运动员与其匹配,经过n次匹配,分别保存每组男女运动员的匹配优势到res数组和最优的男女运动员优势到MaxSum数组。
其中,res数组是N×N的二维数组,用于保存每个男运动员匹配过的女运动员的优势;MaxSum是一个1×N的一维数组,用于保存每个男运动员的匹配的最佳女运动员的优势。

根据题目的输入样例可以得到以下的排列树:
在这里插入图片描述
固定男运动员选女运动员,构成一颗排列数。树的第i行表示第i个男运动员,树结点序号表示与当前行男运动员匹配的女运动员序号。如:第一行的1表示,第一个男运动员与第一个女运动员匹配的竞争优势是20。

剪枝策略

如下是第一步计算得到的MaxSum和res数组:
在这里插入图片描述
如下是第一个分支进行搜索的过程:
在这里插入图片描述

当搜索该子树时,Max=40,表示已经探索过的路线中得到的最优解是40。

此时,在该层进行剪枝的判断:
已经固定的运动员优势和为20+20=40,假设再贪心的加上剩下的运动员匹配优势的最大值为40+MaxSum[2]=40+12=52, 52>40,则还有可能得到更大的优势解,继续向下搜索。

若贪心的加上其余运动员匹配最大优势后,仍不能超过已经搜索出的最优解,那么向下搜完整颗子树也不会得到最优解,则要进行剪枝操作。因为再向下搜索的结果只可能是小于等于最大优势的。
这就是【剪枝操作】的核心思想!
在这里插入图片描述

#include 
using namespace std;int n;
int boy[21][21], girl[21][21];
int Max = INT_MIN; //MAX代表男女双方竞赛优势的总和的最大值 用来返回指定整数类型所能表示的最小值。
int sum = 0;
int res[21][21]; //data[i][j]用于存放男运动员i配对后的双方竞赛优势
int maxSum[21];   //保存每个男生匹配后可达到的最大双方竞赛优势
int book[21];    //标记女运动员是否已经匹配 0未匹配 1已匹配//Max:40 -> 52
void dfs(int t){if(t>=n)  //t到达n后,代表全部标记访问了,得到了最大值{Max = max(Max, sum);return;}int cnt = 0;//求t及t之后男生匹配女生的最大值的和for (int i = t; i < n;i++){cnt += maxSum[i];//假设的贪心的让每个男运动员匹配最优的女运动员}//剪枝函数:之前t个已经匹配好的男女运动员的sum与//之后的t->n-1个男女匹配的最大值加起来得到的Max比较//若前者<=Max,剪枝if(sum+cnt=Max,要继续向下搜索//从第t个男生开始匹配,找未匹配的女生for (int i = 0; i < n;i++){if(!book[i]){//若第i个女生未匹配book[i] = 1;sum += res[t][i];dfs(t + 1);book[i] = 0; //若第t个男生匹配女生i得到的sum不大于Max,则回溯sum -= res[t][i];}}
}int main(){cin >> n;for (int i = 0; i < n;i++){for (int j = 0; j < n;j++){cin >> boy[i][j];}}for (int i = 0; i < n;i++){for (int j = 0; j < n;j++){cin >> girl[i][j];}}for (int i = 0; i < n;i++){for (int j = 0; j < n;j++){//对每个男生都求男女双方竞赛优势,能得到i*j种结果res[i][j] = boy[i][j] * girl[j][i];//记录每个男生匹配后可达到的最大双方竞赛优势,用于后面的剪枝maxSum[i] = max(maxSum[i], res[i][j]);}}dfs(0);cout << Max << endl;return 0;
}

参考博客:运动员最佳匹配问题【回溯算法】

相关内容

热门资讯

普京:难怪您会选这里作为APE... 为期两天的亚太经合组织工商领导人峰会在深圳举行。俄罗斯总统普京在18日的峰会上发表致辞。普京表示,深...
猪价重回9元关口 养殖仍面临亏... 11月17日早上,28个重点监测地区瘦肉型标猪出栏均价为9.12元/公斤,比前一天上涨了一毛钱。尽管...
温泉直播拍顾客还拉黑质疑者 隐... 近日,有网友发帖称,上海汤连得温泉的直播间镜头长期对准洗浴区通往三楼休息区的楼梯通道。这里是顾客上下...
湖北老虎墩墓地出土漆立人凤形勺... 11月18日上午,国家文物局召开“考古中国”重大项目重要进展工作会,发布四项考古最新进展。其中,湖北...
小米回应“雷军深圳发言紧张” ... 在深圳举办的2026年APEC工商领导人峰会上,雷军分享了他对AI现状的看法。他认为技术变化迅速,但...
为何都说“APEC需要中国” ... 2026年APEC工商领导人峰会在深圳举行,吸引了21个经济体的两千多位工商界代表。峰会首日议程紧凑...
黄金会跌回400元一克吗?专家... 黄金会跌回400元一克吗?专家预测不乐观!黄金价格在2024年大幅上涨后,许多人关心2025年的走势...
东风61列装释放战略信号引发岛... 东风-61洲际导弹近日正式列装火箭军,这一消息引发了台湾岛内媒体的广泛关注。据央视网《海峡两岸》节目...
也门首都萨那传出巨大爆炸声 多... 据总台报道员消息,当地时间17日,也门首都萨那传出巨大爆炸声。另据也门胡塞武装消息,沙特阿拉伯主导的...
潮汕牛肉丸圈粉无数中外媒体记者... 潮汕牛肉丸圈粉无数中外媒体记者。11月13日,在APEC会议周新闻中心,浓郁的岭南烟火气在镜头与键盘...
哈啰单车新车型被吐槽“单车刺客... 近日,有网友在北京一路口扫到一辆蓝色新款哈啰单车,页面显示骑行30分钟收费15元,价格远高于普通共享...
女子蹲金价1年不到3万拿下32... “低价加工黄金,只要30元!”近日,在浙江湖州长兴的乡间小路上,这声吆喝吸引了村民刘大妈的注意。远低...
女子腿被压车轮下旁边女子竟指挥... 11月16日(发布),一段网友发布的视频引发热议。视频中,一名女子腿部被压在车轮下,趴在地上痛苦不已...
油价或再下调 今日价格 新一轮... 油价或再下调 今日价格 新一轮调价窗口将启。11月首调油价大跌后,新一轮油价调整有望继续下降。调整窗...
医生建议最近穿袜子睡觉:入睡快... 最近降温,每天晚上钻进被窝就像钻进“冰窖”——躺了半天双脚还是凉的。很多人觉得忍忍就好了,或等睡着就...
陆毅女儿宣布出道,“爸爸去哪儿... 继黄磊女儿10月时尚活动完成“内娱首秀”、郭涛儿子11月入选电影频道2026“星辰大海”青年演员优选...
14岁男孩带内耗妈妈运动治好内... 近日,山东菏泽。一段孩子陪妈妈运动,并喊着:“内耗的妈妈养不出明媚的孩子”的视频火了。记者联系上视频...
新娘强忍泪水与兄弟姐妹吃“分家... 广东汕尾。按照当地习俗,婚礼上新娘与兄弟姐妹吃“分家饭”,新娘强忍泪水,弟弟崩溃大哭,妹妹不敢直视姐...
消防员被困电梯名场面 网友:主... 近日,成都消防开展工作室意外被困电梯于是求救,赶来救援的同行忍不住现场“无情嘲笑”。网友:主打一个自...
男子结婚8年给妻子买10柜子衣... 11月17日(发布),河南长葛的石金龙和妻子罗玉娇结婚8年,最爱给妻子买衣服,“她身材好,穿着好看,...