求矩阵中不同行不同列元素之和的最大值

Question

求矩阵中不同行不同列元素之和的最大值 
假设矩阵A[m][n],为int类型且是已知。
1、从不同行和不同列中取num个数，num=min(m,n)；
2、这num个数之和最大。
如下例A[3][2]：
3 2 
4 3 
5 2 num=min(3,2)=2;找到的值
A[2][0]＝5，A[1][1]＝3，因为他们之和为8，最大。
Comput(int A[][]){...}最好有算法的时间复杂度。有一种基本的方法：
分别不同的行和不同的列取一个数，计算这num个数之和，找到和最大的一个序列并输出。复杂度为O(num!)。希望想法，希望有代码实现。

Answer 1

哦，二分图匹配问题，KM的话，复杂度n^3

Answer 2

var value = from v in array [i] select v;
int s = Array.FindIndex(value.ToArray(), v => v.Equals(value.Max()));
http://topic.csdn.net/u/20100905/13/db6227cb-33ef-42c5-83d3-df459ad3e4e7.html

Answer 3

 
wuyq11
钻石就是不一样啊

Answer 4

好像只解决了矩阵是1*k的算法是吧？有没有实现m*n矩阵的？

Answer 5

LZ不用疑惑了，这个问题用KM或匈牙利算法可以搞定，其他朴素的方法应该是不行的。
KM本身也算是对匈牙利算法的改进，某些特殊情况下，匈牙利会陷入死循环，迭代无法停止。Lz要想了解KM算法，或是独立写出KM的程序，恐怕不是一两天的事情，需要先有些二分图的基础，再搞KM。KM的思想就是，先随机一个匹配，然后为每个顶点给一个标号，建立轮替树不断寻找增广路径，修改顶点的标号，直到找不到新的增广路径为止。本来是n^4的复杂度，但利用广搜，可以让寻找增广路径那块的效率提高，总复杂度降到n^3

Answer 6

wuyq11：给出的方法找不出来
另外：为什么不能遍历？？？从第一行中取一个数
从第二行中取一个满足条件的数

这样就取出来了，不是吗？
这样的复杂度是O(n!)KM算法能不能找到这个组合对应的矩阵坐标？
KM在 O(n^3)的情况下能不能找到一个最优序列？
如果想找到一个最优序列，复杂度是多少？

Answer 7

int[] intArray = { 3, 4, 2, 5, 6, 7, 8, 12, 2, 3, 12 };
            int index = 0;
            List<int> list = new List<int>();
            for (int i = 1; i < intArray.Length; i++)
            {
                if (intArray[index] < intArray[i])
                {
                    list.Clear();
                    index = i;
                    list.Add(i);
                }
                else if (intArray[index] == intArray[i])
                {
                    index = i;
                    list.Add(i);
                }
            }
            Console.WriteLine("最大值:" + intArray[index]);
            Console.WriteLine("下标:");
            for (int i = 0; i < list.Count; i++)
            {
                Console.Write(list[i].ToString() + "  ");
            }