mejor manera de conseguir la mayor suma de una matriz (utilizando Java, pero el algoritmo es el tema aquí)

Question

Lo siento, no sé la terminología correcta de usar, pero tengo una matriz de 3x3 como esto

1 3 4 
5 4 5 
2 2 5 

y quiero obtener el puntaje más alto al elegir un valor de cada fila/columna, pero no puedo elegir la misma fila o columna más de una vez, por lo que la respuesta en este caso es

3 + 5 + 5 = 13 (fila0, col1 + fila1 , col0 + fila2, col2)

4 + 5 + 5 = 14 no está permitido porque habría elegido dos valores de col 2

Estoy usando Java, y normalmente la matriz sería de 15 por 15 en tamaño.

¿Hay un nombre para lo que estoy tratando de hacer, y cuál es el algoritmo

gracias Paul

EDIT: Nota: el algoritmo húngaro sólo funciona cuando ninguna de filas es igual a ninguna de las cols, y en mi Si este no es siempre el caso, regularmente tengo casos de 10x12 o 11x13. Pero parece puede solucionar esto agregando filas ficticias adicionales.

EDITAR hmm, probar uno de estos implmentations y no se parece alwasy a trabajar, a menos que Im leer mal

 
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

Es la assignment problem. Puede ver las filas como "personas" y las columnas como "asignaciones". Desea minimizar (bueno, desea maximizar pero la idea permanece) el costo total, donde cada persona puede hacer una tarea para matrix[i][j] money.

El hungarian algorithm es una buena solución, pero es bastante complicado. Creo que la fuerza bruta funcionará perfectamente en matrices de 15x15.

Answer 2

Para 15x15, puede utilizar Dynamic Programming en O(N 2^N) tiempo, O(2^N) espacio. La idea es utilizar DP con una máscara de bits que indica explícitamente qué columna se utiliza, e implícitamente la fila que está a la altura, algo así como (en 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; 
} 

un seguimiento de los precursores según sea necesario. Esto debería funcionar hasta los 20s bajos.

Para mayores N s, debería considerar las sugerencias de Vlad.