Finding The Max of sum of elements in matrix in distinct rows and columns

I have a nxm matrix and I need to find the maximum of sum of its values in distinct rows and columns.

For example considering the following Matrix:

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

The max will be 12+8+4 = 24

Note that finding the max and eliminating all values belong开发者_JS百科ing to that column or row is not a good solution as it doesn't work for all cases.

The exception for above will be the following:

     m1  m2
n1   17  1
n2   18  15 

If you find 18 and remove 17 and 15, the sum will be 18+1 = 19. while 17+15 = 32 has a higher value.

Any idea about the algorithm for this question?

The solution is to use Hungarian Algorithm. It's a complicated algorithm. There's a very good lecture on that on youtube:

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

This is similar to the N Queen Problem where we have to place N queen in N*N matrix such that no 2 queen should be in the same column or same row.

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));
    }
}