Maximize count of indices with same element by pairing rows from given Matrices | C ++ program for the above approach ; Function to find the maximum defined score ; If all students are assigned ; Check if row is not paired yet ; Check for all indexes ; If values at current indexes are same increase curSum ; Further recursive call ; Store the ans for current mask and return ; Utility function to find the maximum defined score ; Create a mask with all set bits 1 -> row is not paired yet 0 -> row is already paired ; Initialise dp array with - 1 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxScoreSum ( vector < vector < int > > & a , vector < vector < int > > & b , int row , int mask , vector < int > & dp ) { if ( row >= a . size ( ) ) { return 0 ; } if ( dp [ mask ] != -1 ) { return dp [ mask ] ; } int ans = 0 ; for ( int i = 0 ; i < a . size ( ) ; i ++ ) { if ( mask & ( 1 << i ) ) { int newMask = mask ^ ( 1 << i ) ; int curSum = 0 ; for ( int j = 0 ; j < a [ i ] . size ( ) ; j ++ ) { if ( a [ row ] [ j ] == b [ i ] [ j ] ) { curSum ++ ; } } ans = max ( ans , curSum + maxScoreSum ( a , b , row + 1 , newMask , dp ) ) ; } } return dp [ mask ] = ans ; } int maxScoreSumUtil ( vector < vector < int > > & a , vector < vector < int > > & b , int N , int M ) { int row = 0 ; int mask = pow ( 2 , M ) - 1 ; vector < int > dp ( mask + 1 , -1 ) ; return maxScoreSum ( a , b , row , mask , dp ) ; } 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 ; }