Reorganizar una array para maximizar la suma de Bitwise Y de elementos del mismo índice con otra array

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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *