Переупорядочить массив, чтобы максимизировать сумму побитовых И элементов с одинаковым индексом с другим массивом

Учитывая два массива A[] и B[] размера N , задача состоит в том, чтобы найти максимальную сумму побитовых И элементов с одинаковым индексом в массивах A[] и B[] , которую можно получить путем перестановки массив B[] в любом порядке.

Примеры:

Input: A[] = {1, 2, 3, 4}, B[] = {3, 4, 1, 2}
Output: 10
Explanation: One possible way is to obtain the maximum value is to rearrange the array B[] to {1, 2, 3, 4}.
Therefore, sum of Bitwise AND of same-indexed elements of the arrays A[] and B[] = { 1&1 + 2&2 + 3&3 + 4&4 = 10), which is the maximum possible.

Input: A[] = {3, 5, 7, 11}, B[] = {2, 6, 10, 12}
Output: 22

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать на основе следующих наблюдений:

• For each array element of A[] the idea is to chose a not selected array element of B[] using bitmasking which will give maximum bitwise AND sum upto the current index.
• The idea is to useDynamic Programming with bitmasking as it has overlapping subproblems and optimal substructure.
• Suppose, dp(i, mask) represents the maximum bitwise AND sum of array A[] and i, with the selected elements of array B[] represented by bits-position of mask.
• Then the transition from one state to another state can be defined as:
  • For all j in the range [0, N]:
    • If the j^th bit of mask is not set then, dp(i, mask) = max(dp(i, mask|(1<<j))).

Выполните следующие шаги, чтобы решить проблему:

• Определите вектор векторов, который говорит dp размерности N * 2 ^N со значением -1 для хранения всех dp-состояний.
• Определите рекурсивную функцию Dp, скажем, maximandUtil(i, mask), чтобы найти максимальную сумму побитового И элементов в одинаковых соответствующих позициях в обоих массивах A[] и B[] :
  • Базовый случай, если i равно N , верните 0 .
  • Если dp[i][mask] не равно -1 , т.е. уже посещено, верните dp[i][mask].
  • Итерация по диапазону [0, N-1] с использованием переменной j и на каждой итерации. Если j ^-й бит в маске не установлен, обновите dp[i][mask] как dp[i][mask] = max(dp[ i][маска], maximizeUtil(i+1, маска| 2 ^j ).
  • Наконец, верните dp[i][mask].
• Вызовите рекурсивную функцию maximand(0, 0) и выведите возвращаемое ею значение в качестве ответа.

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

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