Нахождение максимума суммы элементов в матрице в отдельных строках и столбцах

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 Queen, где мы должны поместить N queen в матрицу 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));
    }
}