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

Question

我有一个 nxm 矩阵，我需要找到不同行和列中其值之和的最大值。

例如，考虑以下矩阵：

      m1 m2 m3
n1    1  2  3
n2    4  5  6
n3    7  8  9
n4    10 11 12

最大值将为 12+8+4 = 24

请注意，找到最大值并消除属于该列或行的所有值并不是一个好的解决方案，因为它并不适用于所有情况。

上述例外情况如下：

     m1  m2
n1   17  1
n2   18  15 

如果找到 18 并删除 17 和 15，则总和将为 18+1 = 19。而 17+15 = 32 的值更高。

对这个问题的算法有什么想法吗？

Answer 1

解决方案是使用匈牙利算法。这是一个复杂的算法。 youtube 上有一个非常好的讲座：

http://www.youtube.com/watch?v =BUGIhEecipE

Answer 2

这类似于 N 皇后问题，我们必须将 N 皇后放置在 N*N 矩阵中，使得 2 皇后不应该位于同一列或同一行。

import java.util.Vector;

public class maxSum {

    private static int getMaxSum(int row, int[] col, int n, int[][] mat, int sum, 
        Vector<Integer> ans) {
       if(row >= n) {
           System.out.println(ans+"->"+sum);
           return sum;
       }

       int max = Integer.MIN_VALUE;

       for(int i=0;i<n;i++) {
          if(col[i]==1)
              continue;

          col[i] = 1;
          ans.add(mat[row][i]);
          max = Math.max(getMaxSum(row+1,col,n,mat,sum+mat[row][i],ans), max);
          ans.remove(ans.size()-1);
          col[i] = 0;
        }
        return max;
     }

      public static void main(String[] args) {
      // TODO Auto-generated method stub
      int[][] mat = {{2,5,7,6},{8,5,11,9},{7,3,1,2},{8,7,9,7}};
      int n = 4;
      int col[] = {0,0,0,0};
      Vector<Integer> ans = new Vector<Integer>();
      System.out.println(getMaxSum(0,col,n,mat,0,ans));
    }
}