Python学习(5)_运动员的最佳配对问题

    学习Python也有一段时间了,最明显的感受是,Python确实很方便使用,正好也有个算法的作业,就顺便用Python给写了一个运动员最佳配对问题,中间也遇到很多问题,总体上感觉代码写的比较糙。先这样凑合吧,等水平涨了再修改。

算法实现题:Python实现运动员最佳配对问题

1、问题描述:

羽毛球队有男女运动员各n人,给定2个n×n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势;Q[i][j]则是女运动员i和男运动员j配合的女运动员竞赛优势。

由于技术配合和心理状态等各种因素的影响,P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。设计一个算法,计算男女运动员的最佳配对法,使各组男女双方竞赛优势的总和达到最大。

2、编程任务:

设计一个算法,对于给定的男女运动员竞赛优势,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。

3、数据输入:

由文件input.txt给出输入数据;第一行有1个正整数n(1≤n≤20);接下来的2n行,每行n个数,前n行是P,后n行是Q。

4、结果输出:

将计算的男女双方竞赛优势的总和的最大值输出到文件output.txt。

    输入文件示例               输出文件示例

               intput.txt                   output.txt

               3                          52

               10 2 3

               2 3 4

               3 4 5

               2 2 2

               3 5 3

               4 5 1

'''
    运动员最佳配对问题
    @time: 2017年12月15日13:10:34
    @author: allen
'''
'''
    best    
    全局变量
    用以记录最终结果
'''
best = 0

'''
    从文档读入数据
    @param addr 文件地址
    @param mod  文件读取模式
    return list_q,list_p 两个列表 num 人数
'''
def inputdata( addr, mod ):
    '输入文档数据'
    file1 = open( addr, mod )
    file_data = []
    for i in file1.readlines():
        file_data.append( i.rstrip( "\n" ) )
    
    num = int( file_data[0] )
    all_data = []
    for i in file_data[1:]:
        all_data.append( toint( i.split( " " ) ) )
        
    mid = len(all_data)//2
    list_p = all_data[0:mid]
    list_q = all_data[mid:]
    return list_p, list_q, num

'''
    辅助函数:将列表字符数字转化为int类型
    @param lists 待转换列表
    return int类型列表
'''
def toint( lists ):
    '数据处理函数,将各个元素转化为int类型'
    lists= map(int, lists)
    temp = []
    for i in lists:
        temp.append(i)
    return temp

'''
    主函数
    利用回溯法进行最优值检查
'''
def backtrack( t, p, q, n, x ):
    if t > n:
        compute( x, p, q, n )
    else:
        for i in range( t, n+1 ):
            swap( x, i, t )
            backtrack( t+1, p, q, n, x )
            swap( x, i, t )

'''
    交换函数
'''
def swap( x, i, t ):
    tmp = x[t]
    x[t] = x[i]
    x[i] = tmp
    return	

'''
    计算最大值函数
'''
def compute( x, p, q, n ):
    global best
    temp = 0
    for i in range( 0, n ):
        temp += p[i][x[i+1]-1]*q[x[i+1]-1][i]
    #print(temp)
    if best < temp:
        best = temp


'''
    正文开始
    1、读入数据
    2、回溯法计算
'''
p, q, n =  inputdata( "e:/testpython/12_8/input.txt", "r+" )
x = list( range(n+1) )
backtrack( 1, p, q, n, x )
print(best)

'''
    python 3.6.1 的输出结果为:
    ======================================
    52
    ======================================
'''


小艾的博客 http://www.aixinyan.me/