试题详情
简答题 羽毛球队有男女运动员各n人。给定两个n×n的矩阵P和Q。P[i][j]是男运动员i和女运动员j配合组成混合双打的竞赛优势，Q[i][j]是女运动员i和男运动员j配合的竞赛优势。由于技术配合或心理状况等各种因素的影响，P[i][j]并不一定等于Q[j][i]。 采用回溯法设计一个算法，计算男女运动员最佳搭配的配对法，使得各组男女双方竞赛优势乘积的总和达到最大。
  • 对于这个问题，解空间如下：

    在这个解空间中采用回溯方法，由于一个男队员只能和一个女队员搭档，反之也同理，因此，对于搜索的第一步选定某男和某女，那么第二个男队员就不能和第一个男队员的女搭档组合，因此，剪去改女队员的分枝。
    将男女队员的竞赛优势乘积计算出来，然后将各组男女的优势乘积进行相加。找出最大值。

  • 关注下方微信公众号，在线模考后查看

热门试题