Geek Answers Handbook

The best way to get the maximum amount from Matrix (using Java, but the algorithm is the problem)

Sorry, I don’t 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 to get the highest score by selecting a value from each row / column, but I cannot select the same row or column more than once, so the answer is in this case

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

4 + 5 + 5 = 14 is not allowed because I would select two values ​​from col2

I use Java, and usually the matrix will be 15 by 15.

Is there a name for what I'm trying to do and what is an algorithm

thanks Paul

EDIT: Note: the Hungarian algorithm only works when none of the rows is equal to the number of columns, and in my case it is not always the case that I regularly have 10x12 or 11x13 cases. But it seems you can get around this by adding extra dummy lines.

EDIT hmm by trying one of these implications, and it doesn't seem to work unless I understand 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,
+5
2

. "", - "". (, , ) , matrix[i][j] money.

, . , 15x15.

+6

15x15 O(N 2^N) , O(2^N). , DP , , , , , - ( 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;
 }

. 20-.

N s, .

+3

More articles:


All Articles