Rearrange an array to maximize sum of Bitwise AND of same-indexed elements with another array

#include <bits/stdc++.h>

using namespace std;

  

int maximizeAnd(int i, int mask,

                int* A, int* B, int N,

                vector<vector<int> >& dp)

{

    

    if (i == N)

        return 0;

  

    

    

    if (dp[i][mask] != -1)

        return dp[i][mask];

  

    

    for (int j = 0; j < N; ++j) {

  

        

        

        if (!(mask & (1 << j))) {

  

            

            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];

}

  

int maximizeAndUtil(int* A, int* B, int N)

{

    

    vector<vector<int> > dp(

        N, vector<int>(1 << N + 1, -1));

  

    

    

    return maximizeAnd(0, 0, A, B, N, dp);

}

  

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);

}

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets