最佳运动员问题.doc

算法设计与分析 课程设计 题目： 最佳运动员问题 姓名： 班级： 学号： 日期： 一、算法问题描述 羽毛球队有男女运动员各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]。 设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。 二、算法问题形式化表示 编程任务： 设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组 男女双方竞赛优势的总和达到最大。 三、期望输入与输出 输入: 由文件input.txt给出输入数据。第一行有1 个正整数n (1≤n≤20)。接下来的2n行，每行n个数。前n行是p，后n行是q。 输出: 将计算出的男女双方竞赛优势的总和的最大值输出到文件output.txt。 四、算法分析与步骤描述 static class HeapNode implements Comparable{ int s,val; int[] r; HeapNode(int ss,int v,int[] rr){ s = ss; r = rr; for(int i=0;i=n;i++) r[i]=i; } void compute(int ii){ int temp = 0; for(int i= 1;iii;i++){ temp+=p[i][r[i]]*q[r[i]][i]; val = temp; } } public int compareTo(Object x){ int xv = ((HeapNode)x),val; if(valxv) return -1; if(val==xv) return 0; return 1; } } static int n,best=0; static int []bestr; static int[][] p; static int[][] q; static MaxHeap heap = new MaxHeap(); static int getbest(){ HeapNode E = new HeapNode(0,0,new int[n+1]); while(true){ if(E.s==n-1){ if(E.valbest){ bestr=E.r; best=E.val; }else{ for(int i=E.s+1;i=n;i++){ HeapNode N = new HeapNode(E.s+1,E.val.new int[n+1]); for(int j=1;j=n;j++) N.r[j] = E.r[j]; N.r[N.s]=E.r[i]; N.compareTo(N.s); heap.put(N); } } if(heap.isEmpty()) return best; E=(HeapNode)heap.removeMax(); } } } 五、问题实例及算法运算步骤 1.堆结点元素类型是HeapNode解运动员最佳配对问题的优先队列式分支限界法 七、算法复杂度分析 算法的时间复杂度为：