Лучший способ получить самую высокую сумму от Матрицы (использование Java, но алгоритма является проблемой здесь),
Извините я не знаю, что корректная терминология использует, но я имею 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
Править: Примечание: венгерский алгоритм только работает, когда никакие из строк не равняются никаким из седел, и в моем случае это не всегда имеет место, у меня регулярно есть случаи 10x12 или 11x13. Но кажется, что можно обойти это путем добавления дополнительных фиктивных строк.
ОТРЕДАКТИРУЙТЕ хм, испытав один из этих implmentations, и он не делает alwasy, кажется, работают, если я не неправильно читаю его
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,
2 ответа
Это проблема задания. Вы можете рассматривать строки как "люди", а столбцы как "задания". Вы хотите минимизировать (ну, вы хотите максимизировать, но идея остается) общую стоимость, где каждый человек может выполнить одно задание за матрицу[i][j] денег.
Хорошим решением является венгерский алгоритм, но он довольно сложный. Я думаю, что брутфорсинг будет отлично работать на матрицах 15x15.
Для 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-х.
Для больших Ns, вы должны рассмотреть предложения Влада.