Лучший способ получить наибольшую сумму из матрицы (используя Java, но здесь проблема в алгоритме)

Question

Извините, я не знаю правильную терминологию для использования, но у меня есть матрица 3x3, как эта

1 3 4 
5 4 5  
2 2 5  

, и я хочу получить наивысший балл, выбирая значение из каждой строки / столбца, но я не могу выбратьодна и та же строка или столбец более одного раза, поэтому ответ в этом случае будет

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

4 + 5+ 5 = 14 недопустимо, потому что выбрал бы два значения из col2

Я использую Java, и обычно матрица имеет размер 15 на 15.

Есть ли имя длячто я пытаюсь сделать, и что за алгоритм

спасибо Paul

РЕДАКТИРОВАТЬ: Примечание: венгерский алгоритм работает только тогда, когда ни одна из строк не равна ни одной из столбцов, и в моем случае это не всегдаслучай у меня регулярно бывают случаи 10х12 или 11х13.Но, похоже, вы можете обойти это, добавив дополнительные фиктивные строки.

РЕДАКТИРОВАТЬ хм, попробовав одну из этих имплантаций, и она не всегда работает, если только я не читаю ее

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

Это проблема назначения . Вы можете смотреть на строки как «люди», а столбцы как «назначения». Вы хотите минимизировать (ну, вы хотите максимизировать, но идея остается) общую стоимость, где каждый человек может выполнить одно задание за matrix[i][j] money.

Венгерский алгоритм - хорошее решение, но довольно сложное. Я думаю, что брутфорс будет отлично работать на матрицах 15х15.

Answer 2

Для 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 с, вы должны рассмотреть предложения Влада.