Dadas dos arrays A[] y B[] de tamaños N , la tarea es encontrar la suma máxima de Bitwise AND de los mismos elementos indexados en las arrays A[] y B[] que se pueden obtener reorganizando la array B[] en cualquier orden.
Ejemplos:
Entrada: A[] = {1, 2, 3, 4}, B[] = {3, 4, 1, 2}
Salida: 10
Explicación: Una forma posible de obtener el valor máximo es reorganizar la array B[ ] a {1, 2, 3, 4}.
Por lo tanto, la suma de Bitwise AND de los mismos elementos indexados de las arrays A[] y B[] = { 1&1 + 2&2 + 3&3 + 4&4 = 10), que es el máximo posible.Entrada: A[] = {3, 5, 7, 11}, B[] = {2, 6, 10, 12}
Salida: 22
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las permutaciones posibles de la array B[] y, para cada permutación, calcular la suma de Bitwise AND de los mismos elementos indexados en las arrays A[] y B[] y actualizar el máximo suma posible en consecuencia. Finalmente, imprima la suma máxima posible.
Complejidad temporal: O(N! * N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de las siguientes observaciones:
- Para cada elemento de la array de A[], la idea es elegir un elemento de la array no seleccionado de B[] usando máscara de bits , lo que dará el valor máximo de bit a bit Y sumará hasta el índice actual.
- La idea es usar Programación Dinámica con máscara de bits ya que tiene subproblemas superpuestos y una subestructura óptima .
- Supongamos que dp(i, mask) representa la suma AND bit a bit máxima de la array A[] e i , con los elementos seleccionados de la array B[] representados por la posición de bits de mask .
- Entonces la transición de un estado a otro estado se puede definir como:
- Para todo j en el rango [0, N]:
- Si el j -ésimo bit de máscara no está configurado, entonces, dp(i, máscara) = max(dp(i, máscara|(1<<j))).
Siga los pasos a continuación para resolver el problema:
- Defina un vector de vectores dice dp de dimensión N*2 N con valor -1 para almacenar todos los estados de dp.
- Defina una función Dp recursiva, diga maximizarAndUtil(i, máscara) para encontrar la suma máxima de AND bit a bit de los elementos en las mismas posiciones respectivas en ambas arrays A[] y B[] :
- Caso base, si i es igual a N , devuelve 0 .
- Si dp[i][máscara] no es igual a -1 , es decir, ya se ha visitado, devuelva dp[i][máscara].
- Iterar sobre el rango [0, N-1] usando la variable j y en cada iteración, si el j -ésimo bit en la máscara no está configurado, entonces actualice dp[i][máscara] como dp[i][máscara] = max(dp[ i][máscara], maximizarUtil(i+1, máscara| 2 j ).
- Finalmente, devuelve dp[i][máscara].
- Llame a la función recursiva maximizarY(0, 0) e imprima el valor que devuelve como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to implement recursive DP int maximizeAnd(int i, int mask, int* A, int* B, int N, vector<vector<int> >& dp) { // If i is equal to N if (i == N) return 0; // If dp[i][mask] is not // equal to -1 if (dp[i][mask] != -1) return dp[i][mask]; // Iterate over the array B[] for (int j = 0; j < N; ++j) { // If current element // is not yet selected if (!(mask & (1 << j))) { // Update dp[i][mask] dp[i][mask] = max( dp[i][mask], (A[i] & B[j]) + maximizeAnd(i + 1, mask | (1 << j), A, B, N, dp)); } } // Return dp[i][mask] return dp[i][mask]; } // Function to obtain maximum sum // of Bitwise AND of same-indexed // elements from the arrays A[] and B[] int maximizeAndUtil(int* A, int* B, int N) { // Stores all dp-states vector<vector<int> > dp( N, vector<int>(1 << N + 1, -1)); // Returns the maximum value // returned by the function maximizeAnd() return maximizeAnd(0, 0, A, B, N, dp); } // Driver Code int main() { int A[] = { 3, 5, 7, 11 }; int B[] = { 2, 6, 10, 12 }; int N = sizeof A / sizeof A[0]; cout << maximizeAndUtil(A, B, N); }
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Function to implement recursive DP static int maximizeAnd(int i, int mask, int A[], int B[], int N, int[][] dp) { // If i is equal to N if (i == N) return 0; // If dp[i][mask] is not // equal to -1 if (dp[i][mask] != -1) return dp[i][mask]; // Iterate over the array B[] for (int j = 0; j < N; ++j) { // If current element // is not yet selected if ((mask & (1 << j)) == 0) { // Update dp[i][mask] dp[i][mask] = Math.max( dp[i][mask], (A[i] & B[j]) + maximizeAnd(i + 1, mask | (1 << j), A, B, N, dp)); } } // Return dp[i][mask] return dp[i][mask]; } // Function to obtain maximum sum // of Bitwise AND of same-indexed // elements from the arrays A[] and B[] static int maximizeAndUtil(int A[], int B[], int N) { // Stores all dp-states int dp[][] = new int[N][(1 << N) + 1]; for (int dd[] : dp) Arrays.fill(dd, -1); // Returns the maximum value // returned by the function maximizeAnd() return maximizeAnd(0, 0, A, B, N, dp); } // Driver Code public static void main(String[] args) { int A[] = { 3, 5, 7, 11 }; int B[] = { 2, 6, 10, 12 }; int N = A.length; System.out.print(maximizeAndUtil(A, B, N)); } } // This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to implement recursive DP def maximizeAnd(i, mask, A, B, N, dp): # If i is equal to N if (i == N): return 0 # If dp[i][mask] is not # equal to -1 if (dp[i][mask] != -1): return dp[i][mask] # Iterate over the array B[] for j in range(N): # If current element # is not yet selected if ((mask & (1 << j)) == 0): # Update dp[i][mask] dp[i][mask] = max( dp[i][mask],(A[i] & B[j]) + maximizeAnd(i + 1, mask | (1 << j), A, B, N, dp)) # Return dp[i][mask] return dp[i][mask] # Function to obtain maximum sum # of Bitwise AND of same-indexed # elements from the arrays A[] and B[] def maximizeAndUtil(A, B, N): # Stores all dp-states temp = [-1 for i in range(1 << N + 1)] dp = [temp for i in range(N)] # Returns the maximum value # returned by the function maximizeAnd() return maximizeAnd(0, 0, A, B, N, dp) # Driver Code if __name__ == '__main__': A = [ 3, 5, 7, 11 ] B = [ 2, 6, 10, 12 ] N = len(A) print(maximizeAndUtil(A, B, N)) # This code is contributed by ipg2016107
C#
// C# program for the above approach using System; class GFG { // Function to implement recursive DP static int maximizeAnd(int i, int mask, int[] A, int[] B, int N, int[,] dp) { // If i is equal to N if (i == N) return 0; // If dp[i][mask] is not // equal to -1 if (dp[i, mask] != -1) return dp[i, mask]; // Iterate over the array B[] for (int j = 0; j < N; ++j) { // If current element // is not yet selected if ((mask & (1 << j)) == 0) { // Update dp[i][mask] dp[i, mask] = Math.Max( dp[i, mask], (A[i] & B[j]) + maximizeAnd(i + 1, mask | (1 << j), A, B, N, dp)); } } // Return dp[i][mask] return dp[i, mask]; } // Function to obtain maximum sum // of Bitwise AND of same-indexed // elements from the arrays A[] and B[] static int maximizeAndUtil(int[] A, int[] B, int N) { // Stores all dp-states int[,] dp = new int[N, (1 << N) + 1]; for(int i = 0; i<N; i++) { for(int j =0 ; j<(1 << N) + 1; j++) { dp[i, j] = -1; } } // Returns the maximum value // returned by the function maximizeAnd() return maximizeAnd(0, 0, A, B, N, dp); } // Driver Code static void Main() { int[] A = { 3, 5, 7, 11 }; int[] B = { 2, 6, 10, 12 }; int N = A.Length; Console.Write(maximizeAndUtil(A, B, N)); } } // This code is contributed by sanjoy_62.
Javascript
<script> // Javascript program for the above approach // Function to implement recursive DP function maximizeAnd(i, mask, A, B, N, dp) { // If i is equal to N if (i == N) return 0; // If dp[i][mask] is not // equal to -1 if (dp[i][mask] != -1) return dp[i][mask]; // Iterate over the array B[] for(var j = 0; j < N; ++j) { // If current element // is not yet selected if (!(mask & (1 << j))) { // Update dp[i][mask] dp[i][mask] = Math.max( dp[i][mask], (A[i] & B[j]) + maximizeAnd(i + 1, mask | (1 << j), A, B, N, dp)); } } // Return dp[i][mask] return dp[i][mask]; } // Function to obtain maximum sum // of Bitwise AND of same-indexed // elements from the arrays A[] and B[] function maximizeAndUtil(A, B, N) { // Stores all dp-states var dp = Array.from( Array(N), () => Array(1 << N + 1).fill(-1)); // Returns the maximum value // returned by the function maximizeAnd() return maximizeAnd(0, 0, A, B, N, dp); } // Driver Code var A = [ 3, 5, 7, 11 ]; var B = [ 2, 6, 10, 12 ]; var N = A.length document.write(maximizeAndUtil(A, B, N)); // This code is contributed by rrrtnx </script>
22
Complejidad de Tiempo: O (N 2 * 2 N)
Espacio Auxiliar: O (N * 2 N )
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA