Dadas dos arrays binarias 2D , a[][] y b[][], ambas de tamaño M*N , la tarea es emparejar cada fila de la array a[][] con cualquier fila de la array b[][]de modo que la puntuación total se pueda maximizar y la puntuación de cada par se calcule como los índices totales en los que los valores de ambas filas son idénticos.
Nota: cada fila de la array b[][] solo se puede emparejar con una sola fila de vectorun[][] .
Ejemplos:
Entrada: a[][] = {{1, 1, 0}, {1, 0, 1}, {0, 0, 1}}, b[][] = {{1, 0, 0}, { 0, 0, 1}, {1, 1, 0}}
Salida: 8
Explicación:
Considere el emparejamiento de filas en el siguiente orden, para maximizar el puntaje total obtenido:
- La fila 0 de a[][] emparejada con la fila 2 de b[][] tiene una puntuación de 3.
- La fila 1 de a[][] emparejada con la fila 0 de b[][] con una puntuación de 2.
- La fila 2 de a[][] emparejada con la fila 1 de b[][] con una puntuación de 3.
Por tanto, la suma de las puntuaciones obtenidas es 3 + 2 + 3 = 8.
Entrada: a[][] = {{0, 0}, {0, 0}, {0, 0}}, b[][] = {{1, 1}, {1, 1}, {1, 1}}
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las permutaciones posibles de las filas de los arreglos a[][] y para cada permutación del arreglo a[][] , encontrar la suma de las puntuaciones de cada par correspondiente y si es mayor que la respuesta actual , actualice la respuesta al valor de la suma actual de puntajes. Después de comprobar todos los pares, imprima la puntuación máxima obtenida.
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 find the maximum score
void maxScoreSum(vector<vector<int> >& a,
vector<vector<int> >& b)
{
// Stores the maximum sum of scores
int maxSum = 0;
vector<int> pos;
for (int i = 0; i < a.size(); i++) {
pos.push_back(i);
}
// For each permutation of pos vector
// calculate the score
do {
int curSum = 0;
for (int i = 0; i < a.size(); i++) {
for (int j = 0;
j < a[pos[i]].size(); j++) {
// If values at current indexes
// are same then increment the
// current score
curSum += (a[pos[i]][j] == b[i][j]);
maxSum = max(maxSum, curSum);
}
}
} while (next_permutation(pos.begin(), pos.end()));
// Print the maximum score
cout << maxSum;
}
// Driver Code
int main()
{
int N = 3, M = 3;
vector<vector<int> > a
= { { 1, 1, 0 }, { 1, 0, 1 }, { 0, 0, 1 } };
vector<vector<int> > b
= { { 1, 0, 0 }, { 0, 0, 1 }, { 1, 1, 0 } };
maxScoreSum(a, b);
return 0;
}
Python3
# Python Program to implement # the above approach def next_permutation(array): i = len(array) - 1 while (i > 0 and array[i - 1] >= array[i]): i -= 1 if (i <= 0): return False j = len(array) - 1 while (array[j] <= array[i - 1]): j -= 1 temp = array[i - 1] array[i - 1] = array[j] array[j] = temp j = len(array) - 1 while (i < j): temp = array[i]; array[i] = array[j]; array[j] = temp; i += 1 j -= 1 return array # Function to find the maximum score def maxScoreSum(a, b): # Stores the maximum sum of scores maxSum = 0 pos = [] for i in range(len(a)): pos.append(i) # For each permutation of pos vector # calculate the score while(True): curSum = 0 for i in range(len(a)): for j in range(len(a[pos[i]])): # If values at current indexes # are same then increment the # current score curSum += (a[pos[i]][j] == b[i][j]) maxSum = max(maxSum, curSum) if(next_permutation(pos) == False): break # Print the maximum score print(maxSum) # Driver Code N, M = 3, 3 a = [[1, 1, 0], [1, 0, 1], [0, 0, 1]] b = [[1, 0, 0], [0, 0, 1], [1, 1, 0]] maxScoreSum(a, b) # This code is contributed by shinjanpatra
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
public static List<List<int>> perms = new List<List<int>>();
public static void generate_permuatation(int mask, int ind, int N, List<int> current){
if(ind == N){
List<int> temp = new List<int>(current);
perms.Add(temp);
return;
}
for(int i = 0 ; i < N ; i++){
if(((mask >> i) & 1) == 0){
current.Add(i);
generate_permuatation(mask | (1 << i), ind + 1, N, current);
current.RemoveAt(current.Count-1);
}
}
}
// Function to find the maximum score
public static void maxScoreSum(List<List<int>> a, List<List<int>> b)
{
// Stores the maximum sum of scores
int maxSum = 0;
generate_permuatation(0, 0, a.Count, new List<int>());
// For each permutation of {0, a.Count - 1} vector
// calculate the score
for(int ind = 0 ; ind < perms.Count ; ind++){
List<int> pos = perms[ind];
int curSum = 0;
for (int i = 0; i < a.Count ; i++) {
for (int j = 0 ; j < a[pos[i]].Count ; j++) {
// If values at current indexes
// are same then increment the
// current score
curSum += (a[pos[i]][j] == b[i][j] ? 1 : 0);
maxSum = Math.Max(maxSum, curSum);
}
}
}
// Print the maximum score
Console.Write(maxSum);
}
// Driver Code
public static void Main(string[] args){
// int N = 3;
// int M = 3;
List<List<int>> a = new List<List<int>>{
new List<int>{ 1, 1, 0 },
new List<int>{ 1, 0, 1 },
new List<int>{ 0, 0, 1 }
};
List<List<int>> b = new List<List<int>>{
new List<int>{ 1, 0, 0 },
new List<int>{ 0, 0, 1 },
new List<int>{ 1, 1, 0 }
};
maxScoreSum(a, b);
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// JavaScript Program to implement
// the above approach
function next_permutation(array) {
var i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i]) {
i--;
}
if (i <= 0) {
return false;
}
var j = array.length - 1;
while (array[j] <= array[i - 1]) {
j--;
}
var temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;
j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
return array;
}
// Function to find the maximum score
function maxScoreSum(a, b) {
// Stores the maximum sum of scores
let maxSum = 0;
let pos = [];
for (let i = 0; i < a.length; i++) {
pos.push(i);
}
// For each permutation of pos vector
// calculate the score
do {
let curSum = 0;
for (let i = 0; i < a.length; i++) {
for (let j = 0;
j < a[pos[i]].length; j++) {
// If values at current indexes
// are same then increment the
// current score
curSum += (a[pos[i]][j] == b[i][j]);
maxSum = Math.max(maxSum, curSum);
}
}
} while (next_permutation(pos));
// Print the maximum score
document.write(maxSum);
}
// Driver Code
let N = 3, M = 3;
let a
= [[1, 1, 0], [1, 0, 1], [0, 0, 1]];
let b
= [[1, 0, 0], [0, 0, 1], [1, 1, 0]];
maxScoreSum(a, b);
// This code is contributed by Potta Lokesh
</script>
Producción:
8
Complejidad de Tiempo: O(N*M*M!), donde M! son el número de permutaciones y N*M para calcular la puntuación de cada par.
Espacio Auxiliar: O(M)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando el concepto de máscara de bits . La idea es que para cada fila en el vector a[][] , pruebe todas las filas en el vector b[][] que no se hayan elegido antes. Use una máscara de bits para representar las filas ya elegidas del vector b[][] . Para evitar volver a calcular el mismo subproblema, memorice el resultado de cada máscara de bits . Siga los pasos a continuación para resolver el problema:
- Inicialice la fila de variables como 0, enmascare como (2 M – 1) .
- Inicialice el vector dp[] de máscara de tamaño + 1 con valores -1 .
- Si la fila es mayor que igual a a.size() , devuelva 0 y si dp[mask] no es igual a -1 , devuelva dp[mask] .
- Inicialice la variable ans como 0 para almacenar la respuesta.
- Iterar sobre el rango [0, a.size()) usando la variable i y realizar las siguientes tareas:
- Si el AND bit a bit de mask y 2 i es verdadero , entonces inicialice la variable newMask como mask^(1<<i) y curSum como 0 .
- Itere sobre el rango [0, a[i].size()) usando la variable j y si a[row][j] es igual a b[i][j] entonces aumente el valor de curSum en 1 .
- Establezca el valor de ans como el máximo de ans o curSum + maxScoreSum(a, b, row+1, newmask, dp) recursivamente .
- Después de realizar los pasos anteriores, establezca el valor de dp[máscara] como ans y devuelva el valor de ans 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 find the maximum defined
// score
int maxScoreSum(vector<vector<int> >& a,
vector<vector<int> >& b,
int row, int mask,
vector<int>& dp)
{
// If all students are assigned
if (row >= a.size()) {
return 0;
}
if (dp[mask] != -1) {
return dp[mask];
}
int ans = 0;
for (int i = 0; i < a.size(); i++) {
// Check if row is not paired yet
if (mask & (1 << i)) {
int newMask = mask ^ (1 << i);
int curSum = 0;
// Check for all indexes
for (int j = 0; j < a[i].size(); j++) {
// If values at current indexes
// are same increase curSum
if (a[row][j] == b[i][j]) {
curSum++;
}
}
// Further recursive call
ans = max(
ans, curSum
+ maxScoreSum(
a, b, row + 1,
newMask, dp));
}
}
// Store the ans for current
// mask and return
return dp[mask] = ans;
}
// Utility function to find the maximum
// defined score
int maxScoreSumUtil(vector<vector<int> >& a,
vector<vector<int> >& b,
int N, int M)
{
int row = 0;
// Create a mask with all set bits
// 1 -> row is not paired yet
// 0 -> row is already paired
int mask = pow(2, M) - 1;
// Initialise dp array with -1
vector<int> dp(mask + 1, -1);
return maxScoreSum(a, b, row, mask, dp);
}
// Driver Code
int main()
{
int N = 3, M = 3;
vector<vector<int> > a
= { { 1, 1, 0 }, { 1, 0, 1 }, { 0, 0, 1 } };
vector<vector<int> > b
= { { 1, 0, 0 }, { 0, 0, 1 }, { 1, 1, 0 } };
cout << maxScoreSumUtil(a, b, N, M);
return 0;
}
Python3
# Python 3 program for the above approach # Function to find the maximum defined # score def maxScoreSum(a, b, row, mask, dp): # If all students are assigned if (row >= len(a)): return 0 if (dp[mask] != -1): return dp[mask] ans = 0 for i in range(len(a)): # Check if row is not paired yet if (mask & (1 << i)): newMask = mask ^ (1 << i) curSum = 0 # Check for all indexes for j in range(len(a[i])): # If values at current indexes # are same increase curSum if (a[row][j] == b[i][j]): curSum += 1 # Further recursive call ans = max( ans, curSum + maxScoreSum( a, b, row + 1, newMask, dp)) # Store the ans for current # mask and return dp[mask] = ans return dp[mask] # Utility function to find the maximum # defined score def maxScoreSumUtil(a, b, N, M): row = 0 # Create a mask with all set bits # 1 -> row is not paired yet # 0 -> row is already paired mask = pow(2, M) - 1 # Initialise dp array with -1 dp = [-1]*(mask + 1) return maxScoreSum(a, b, row, mask, dp) # Driver Code if __name__ == "__main__": N = 3 M = 3 a = [[1, 1, 0], [1, 0, 1], [0, 0, 1]] b = [[1, 0, 0], [0, 0, 1], [1, 1, 0]] print(maxScoreSumUtil(a, b, N, M)) # This code is contributed by ukasp.
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the maximum defined
// score
public static int maxScoreSum(List<List<int>> a, List<List<int>> b, int row, int mask, List<int> dp)
{
// If all students are assigned
if (row >= a.Count){
return 0;
}
if (dp[mask] != -1){
return dp[mask];
}
int ans = 0;
for (int i = 0 ; i < a.Count ; i++) {
// Check if row is not paired yet
if ((mask & (1 << i)) > 0){
int newMask = mask ^ (1 << i);
int curSum = 0;
// Check for all indexes
for (int j = 0; j < a[i].Count ; j++) {
// If values at current indexes
// are same increase curSum
if (a[row][j] == b[i][j]) {
curSum++;
}
}
// Further recursive call
ans = Math.Max(ans, curSum + maxScoreSum(a, b, row + 1, newMask, dp));
}
}
// Store the ans for current
// mask and return
return dp[mask] = ans;
}
// Utility function to find the maximum
// defined score
public static int maxScoreSumUtil(List<List<int>> a, List<List<int>> b, int N,int M)
{
int row = 0;
// Create a mask with all set bits
// 1 -> row is not paired yet
// 0 -> row is already paired
int mask = (int)Math.Pow(2, M) - 1;
// Initialise dp array with -1
List<int> dp = new List<int>();
for(int i = 0 ; i <= mask ; i++){
dp.Add(-1);
}
return maxScoreSum(a, b, row, mask, dp);
}
// Driver Code
public static void Main(string[] args){
int N = 3;
int M = 3;
List<List<int>> a = new List<List<int>>{
new List<int>{ 1, 1, 0 },
new List<int>{ 1, 0, 1 },
new List<int>{ 0, 0, 1 }
};
List<List<int>> b = new List<List<int>>{
new List<int>{ 1, 0, 0 },
new List<int>{ 0, 0, 1 },
new List<int>{ 1, 1, 0 }
};
Console.Write(maxScoreSumUtil(a, b, N, M));
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// JavaScript code for the approach
// Function to find the maximum defined
// score
function maxScoreSum(a, b, row, mask, dp){
// If all students are assigned
if (row >= a.length)
return 0
if (dp[mask] != -1)
return dp[mask]
let ans = 0
for(let i=0;i<a.length;i++){
// Check if row is not paired yet
if (mask & (1 << i)){
newMask = mask ^ (1 << i)
curSum = 0
// Check for all indexes
for(let j=0;j<a[i].length;j++){
// If values at current indexes
// are same increase curSum
if (a[row][j] == b[i][j])
curSum += 1
}
// Further recursive call
ans = Math.max(ans, curSum + maxScoreSum(a, b, row + 1,newMask, dp))
}
}
// Store the ans for current
// mask and return
dp[mask] = ans
return dp[mask]
}
// Utility function to find the maximum
// defined score
function maxScoreSumUtil(a,b,N, M){
let row = 0
// Create a mask with all set bits
// 1 -> row is not paired yet
// 0 -> row is already paired
let mask = Math.pow(2, M) - 1
// Initialise dp array with -1
let dp = new Array(mask + 1).fill(-1)
return maxScoreSum(a, b, row, mask, dp)
}
// Driver Code
let N = 3
let M = 3
let a = [[1, 1, 0], [1, 0, 1], [0, 0, 1]]
let b = [[1, 0, 0], [0, 0, 1], [1, 1, 0]]
document.write(maxScoreSumUtil(a, b, N, M),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
8
Complejidad de Tiempo: O(2 M *M*N)
Espacio Auxiliar: O(2 M )