Somme maximale d’une matrice où chaque valeur provient d’une ligne et d’une colonne uniques

Donné un matrice de taille NXNla tâche consiste à trouver la somme maximale de cette matrice où chaque valeur sélectionnée provient d’une colonne unique pour chaque ligne.
Exemples:

Input: matrix = [[3, 4, 4, 4],
                 [1, 3, 4, 4], 
                 [3, 2, 3, 4], 
                 [4, 4, 4, 4]]
Output: 16
Explanation:
Selecting (0, 1) from row 1 = 4
Selecting (1, 2) from row 2 = 4
Selecting (2, 3) from row 3 = 4
Selecting (3, 0) from row 4 = 4
Therefore, max sum = 4 + 4 + 4 + 4 = 16
                        
Input: matrix = [[0, 1, 0, 1], 
                 [3, 0, 0, 2], 
                 [1, 0, 2, 0], 
                 [0, 2, 0, 0]]
Output: 8
Explanation: 
Selecting (0, 3) from row 1 = 1
Selecting (1, 0) from row 2 = 3
Selecting (2, 2) from row 3 = 2
Selecting (3, 1) from row 4 = 2
Therefore, max sum = 1 + 3 + 2 + 2 = 8

Approcher:

  • Générer une chaîne numérique de taille N contenant des nombres de 1 à N
  • Trouver la permutation de cette chaîne (N!).
  • L’appariement se fait maintenant entre les permutations, de sorte que chaque N! l’appariement a une colonne unique pour chaque ligne.
  • Calculez ensuite la somme des valeurs de toutes les paires.

Voici la mise en œuvre de l’approche ci-dessus :

Python3

from itertools import permutations

def MaxSum(side, matrix):

        

    s = ''

    

    for i in range(0, side):

        s = s + str(i)

    

    permlist = permutations(s)

    

    

    cases = []

    

    

    for perm in list(permlist):

        cases.append(''.join(perm))

    

    

    sum = []

    

    

    for c in cases:

        p = []

        tot = 0

        for i in range(0, side):

            p.append(matrice[int(s[i])][int(c[i])])

        p.sort()

        for i in range(side-1, -1, -1):

            tot = tot + p[i]

        sum.append(tot)

    

    

    

    print(max(sum))

        

if __name__ == '__main__':

    

    side = 4

    matrix = [[3, 4, 4, 4], [1, 3, 4, 4], [3, 2, 3, 4], [4, 4, 4, 4]]

    MaxSum(side, matrix)

    side = 3

    matrix = [[1, 2, 3], [6, 5, 4], [7, 9, 8]]

    MaxSum(side, matrix)

Complexité temporelle : D’ACCORD)où K = N!
Complexité de l’espace auxiliaire : D’ACCORD)où K = N!

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut