Best way to get the highest sum from a Matrix (using Java but algorithm is the issue here)

Question

Sorry I dont know the correct terminology to use but I have a 3x3 matrix like this

1 3 4 
5 4 5  
2 2 5  

and I want get the highest score by picking a value from each row/column but I cant pick the same row or column more than once , so the answer in this case is

3 + 5 + 5 = 13 (row0,col1 + row1,col0 + row2,col2)

4 + 5 + 5 = 14 is not allowed because would have picked two values from col2

I'm using Java, and typically the matrix would be 15 by 15 in size.

Is there a name for what Im trying to do, and whats the algorithm

thanks Paul

EDIT:Note:the hungarian algorithm only works when no of rows equals no of cols, and in my case this is not always the case I regularly have cases of 10x12 or 11x13. But it appears you can get round this by adding extra dummy rows.

EDIT hmm, trying out one of these implmentations and it doesnt alwasy seem to work, unless Im misreading it

100.0,100.0,100.0,100.0,30.0,80.0,80.0,100.0,100.0,80.0,
80.0,100.0,100.0,100.0,80.0,80.0,25.0,100.0,100.0,80.0,
80.0,100.0,100.0,100.0,80.0,25.0,80.0,100.0,100.0,80.0,
100.0,25.0,80.0,100.0,100.0,100.0,100.0,100.0,100.0,100.0,
0.0,100.0,100.0,100.0,100.0,80.0,80.0,100.0,100.0,100.0,
100.0,100.0,100.0,100.0,100.0,100.0,100.0,100.0,25.0,100.0,
100.0,100.0,100.0,25.0,100.0,100.0,100.0,75.0,100.0,100.0,
100.0,80.0,30.0,100.0,75.0,100.0,100.0,100.0,100.0,100.0,
100.0,100.0,100.0,100.0,80.0,80.0,80.0,100.0,100.0,25.0,
100.0,100.0,100.0,75.0,100.0,100.0,100.0,25.0,100.0,100.0,
Results calculated
0:4,0,
1:3,1,
2:7,2,
3:6,3,
4:0,4,
5:2,5,
6:1,6,
7:9,7,
8:5,8,
9:8,9,

Answer 1

It's the assignment problem. You can look at the rows as "people" and the columns as "assignments". You want to minimise (well, you want to maximise but the idea remains) the total cost, where each person can do one task for matrix[i][j] money.

The hungarian algorithm is a good solution, but it is fairly complicated. I think bruteforcing it will work just fine on 15x15 matrices.

Answer 2

For 15x15, you can use Dynamic Programming in O(N 2^N) time, O(2^N) space. The idea is to use DP with a bitmask indicating explicitly which column is used, and implicitly which row you are up to, something like (in C):

/* used, cache arrays of size 1 << N, used initialized to 0 */

/* max_sum( 0, 0 ) is the starting point.  Row is implicit, but 
     here to make things easier. */
int max_sum( int row, int bitmask ) { 
      /* Base case - the number of rows */
      if ( row == num_row ) return 0;

      /* If we've already seen this bitmask */
      if ( used[ bitmask ] ) return cache[ bitmask ];
      int max_current = 0, i;

      for ( i = 0; i < N; i++ )
          /* If column "i" is not used */
          if ( ( bitmask & ( 1 << i ) ) == 0 )
              max_current = max( 
                             /* Use column i on this row, mark column as used
                                   on the bitmask, go on to the next row. */
                             max_sum( row + 1, bitmask | ( 1 << i ) ) 
                                 + cell[row][i],
                             max_current )

      /* Save the cache down */
      used[ bitmask ] = 1;
      return cache[ bitmask ] = max_current;
 }

Keep track of the precursor as necessary. This should work up to the low 20s.

For bigger Ns, you should consider Vlad's suggestions.