C#算法求解最佳组队问题

  • C#算法求解最佳组队问题已关闭评论
  • 100 次浏览
  • A+
所属分类:.NET技术
摘要

双人混合ACM程序设计竞赛即将开始,因为是双人混合赛,故每支队伍必须由1男1女组成。现在需要对n名男队员和n名女队员进行配对。由于不同队员之间的配合优势不一样,因此,如何组队成了大问题。
给定n×n优势矩阵P,其中P[i][j]表示男队员i和女队员j进行组队的竞赛优势(0<P[i][j]<10000)。设计一个算法,计算男女队员最佳配对法,使组合出的n支队伍的竞赛优势总和达到最大。


最佳组队问题

双人混合ACM程序设计竞赛即将开始,因为是双人混合赛,故每支队伍必须由1男1女组成。现在需要对n名男队员和n名女队员进行配对。由于不同队员之间的配合优势不一样,因此,如何组队成了大问题。
给定n×n优势矩阵P,其中P[i][j]表示男队员i和女队员j进行组队的竞赛优势(0<P[i][j]<10000)。设计一个算法,计算男女队员最佳配对法,使组合出的n支队伍的竞赛优势总和达到最大。

输入格式:

测试数据有多组,处理到文件尾。每组测试数据首先输入1个正整数n(1≤n≤9),接下来输入n行,每行n个数,分别代表优势矩阵P的各个元素。

输出格式:

对于每组测试,在一行上输出n支队伍的竞赛优势总和的最大值。

输入样例:

3 10 2 3 2 3 4 3 4 5 

输出样例:

18 

算法实现:

public  class Program {     //输入的整数     public static int n = 0;     //输入的n行,每行n个数     public static string line;     //book数组标记访问过的列     public static int[] book;     public static int maxsum = 0;     public static int[,] P;     public static void Main()     {         while (true)         {             string N =System.Console.ReadLine();             if(N == null || N == "")             {                 break;             }             n = int.Parse(N);             //矩阵P             P = new int[n, n];             book = new int[n];             int i = 0;             while ((line = System.Console.ReadLine()) != null)             {                 //获取的line肯定为数组 一行里面有n个数                 //存入数组然后添加进入P矩阵                 //存入矩阵                 string[] np = line.Split(' ');                 for (int j = 0; j < np.Length; j++)                 {                     P[i, j] = System.Convert.ToInt32(np[j]);                 }                 i++;                 if(i > n - 1)                 {                     break;                 }             }             maxsum = 0;             def(0, 0);             System.Console.WriteLine(maxsum);         }     }     public static void def(int i, int c)     {         if (i > n - 1)         {             if (c > maxsum) { maxsum = c; }             return;         }         for (int j = 0; j < n; j++)         {             if (book[j] == 0)             {                 book[j] = 1;                 //Console.Write(P[i, j] + " ");                 def(i + 1, c + P[i, j]);                 book[j] = 0;             }         }     } } 

各位C#大佬有没有时间复杂度更低的方法去解这个题目