Максимальное количество индексов с одним и тем же элементом путем объединения строк из заданных матриц

Имея два двумерных двоичных массива, a[][] и b[][] оба размера M*N , задача состоит в том, чтобы соединить каждую строку в массиве a[][] с любой строкой в массиве b[][] таким образом, что общий балл может быть максимальным, а балл для каждой пары рассчитывается как сумма индексов, при которых значения обеих строк идентичны.

Примечание. Каждая строка массива b[][] может быть связана только с одной строкой вектора а[][] .

Примеры:

Input: a[][] = {{1, 1, 0}, {1, 0, 1}, {0, 0, 1}}, b[][] = {{1, 0, 0}, {0, 0, 1}, {1, 1, 0}}
Output: 8
Explanation:
Consider the pairing of rows in the following order, to maximize the total score obtained:

• Row 0 of a[][] paired with row 2 of b[][] has the score of 3.
• Row 1 of a[][] paired with row 0 of b[][] with score of 2.
• Row 2 of a[][] paired with row 1 of b[][] with score of 3.

Therefore, the sum of scores obtained is 3 + 2 + 3 = 8.

Input: a[][] = {{0, 0}, {0, 0}, {0, 0}}, b[][] = {{1, 1}, {1, 1}, {1, 1}}
Output: 0

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные перестановки строк массивов a[][] и для каждой перестановки массива a[][] найти сумму баллов каждой соответствующей пары , и если он больше, чем текущий ответ , обновить ответ до значения текущей суммы баллов. После проверки всех пар выведите максимальное количество баллов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M*M!), где M! - количество перестановок и N * M для расчета оценки каждой пары.
Вспомогательное пространство: O(M)

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью концепции битовой маскировки. Идея состоит в том, чтобы для каждой строки в векторе a[][] попробовать все строки в векторе b[][] , которые не были выбраны ранее. Используйте битовую маску для представления уже выбранных строк вектора b[][] . Чтобы избежать повторного вычисления одной и той же подзадачи, запомните результат для каждой битовой маски. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте строку переменных как 0, замаскируйте как (2 ^M – 1) .
• Инициализируйте вектор dp[] размера mask + 1 со значениями -1 .
• Если строка больше, чем равна a.size() , верните 0 , а если dp[mask] не равно -1 , верните dp[mask] .
• Инициализируйте переменную ans как 0 , чтобы сохранить ответ.
• Перебрать диапазон [0, a.size()) с помощью переменной i и выполнить следующие задачи:
  • Если побитовое И маски и 2 ⁱ истинно , тогда инициализируйте переменную newMask как mask^(1<<i) и curSum как 0 .
  • Переберите диапазон [0, a[i].size()) с использованием переменной j , и если a[row][j] равно b[i][j] , увеличьте значение curSum на 1 .
  • Установите значение ans как максимальное значение ans или curSum + maxScoreSum(a, b, row+1, newmask, dp) рекурсивно.
• После выполнения вышеуказанных шагов установите значение dp[mask] в качестве ответа и верните значение ответа в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(2 ^M *M*N)
Вспомогательное пространство: O(2 ^м )