class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
}
};
1947. 最大兼容性评分和
有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0（no，否），要么是 1（yes，是）。
这份调查问卷被分发给 m 名学生和 m 名导师，学生和导师的编号都是从 0 到 m - 1 。学生的答案用一个二维整数数组 students 表示，其中 students[i] 是一个整数数组，包含第 i 名学生对调查问卷给出的答案（下标从 0 开始）。导师的答案用一个二维整数数组 mentors 表示，其中 mentors[j] 是一个整数数组，包含第 j 名导师对调查问卷给出的答案（下标从 0 开始）。
每个学生都会被分配给 一名 导师，而每位导师也会分配到 一名 学生。配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。
[1, 0, 1] 而导师答案为 [0, 0, 1] ，那么他们的兼容性评分为 2 ，因为只有第二个和第三个答案相同。请你找出最优的学生与导师的配对方案，以 最大程度上 提高 兼容性评分和 。
给你 students 和 mentors ，返回可以得到的 最大兼容性评分和 。
示例 1：
输入：students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]] 输出：8 解释：按下述方式分配学生和导师： - 学生 0 分配给导师 2 ，兼容性评分为 3 。 - 学生 1 分配给导师 0 ，兼容性评分为 2 。 - 学生 2 分配给导师 1 ，兼容性评分为 3 。 最大兼容性评分和为 3 + 2 + 3 = 8 。
示例 2：
输入：students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]] 输出：0 解释：任意学生与导师配对的兼容性评分都是 0 。
提示：
m == students.length == mentors.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k] 为 0 或 1mentors[j][k] 为 0 或 1原站题解
python3 解法, 执行用时: 220 ms, 内存消耗: 60.2 MB, 提交时间: 2022-12-08 11:50:36
import numpy as np
from scipy.optimize import linear_sum_assignment
'''
构造student和mentor之间的匹配分数矩阵，然后找到总分最大的索引即可
（注意linear_sum_assignment只能找最小位置的索引，所以要构造一个weakAt）
'''
class Solution:
def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
match_matrix = np.zeros((len(students), len(mentors)))
for i, stu in enumerate(students):
for j, men in enumerate(mentors):
score = 0
for s,m in zip(stu,men):
if s == m:
score += 1
match_matrix[i,j] = score
weakAt = len(students[0]) - match_matrix
row_ind,col_ind=linear_sum_assignment(weakAt)
return int(match_matrix[row_ind,col_ind].sum())
python3 解法, 执行用时: 1004 ms, 内存消耗: 15.2 MB, 提交时间: 2022-12-08 11:49:33
class Solution:
def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
m = len(students) #老师和学生的人数
n = len(students[0]) #n个问题
#---- 预计算学生和老师的匹配得分
score = [[0 for _ in range(m)] for _ in range(m)]
for i,stu in enumerate(students):
for j,men in enumerate(mentors):
cur = 0
for st, me in zip(stu, men):
cur += (st == me)
score[i][j] = cur
#-------------------- 回溯 ----------------------#
used = [False for _ in range(m)]
self.cur = 0
self.max_ = 0
def backtrace(si: int) -> None:
if si == m:
self.max_ = max(self.max_, self.cur)
return
for j in range(m):
if used[j] == False:
self.cur += score[si][j]
used[j] = True
backtrace(si + 1)
used[j] = False
self.cur -= score[si][j]
backtrace(0)
return self.max_
python3 解法, 执行用时: 48 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-08 11:47:52
class Solution:
def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
m, n = len(students), len(students[0])
g = [[0] * m for _ in range(m)]
for i in range(m):
for j in range(m):
for k in range(n):
g[i][j] += int(students[i][k] == mentors[j][k])
f = [0] * (1 << m)
for mask in range(1, 1 << m):
c = bin(mask).count("1")
for i in range(m):
# 判断 mask 的第 i 位是否为 1
if mask & (1 << i):
f[mask] = max(f[mask], f[mask ^ (1 << i)] + g[c - 1][i])
return f[(1 << m) - 1]
python3 解法, 执行用时: 952 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-08 11:47:03
class Helper:
@staticmethod
def nextPermutation(nums: List[int]) -> bool:
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i < 0:
return False
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[i] >= nums[j]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return True
class Solution:
def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
m, n = len(students), len(students[0])
g = [[0] * m for _ in range(m)]
for i in range(m):
for j in range(m):
for k in range(n):
g[i][j] += int(students[i][k] == mentors[j][k])
p = list(range(m))
ans = 0
while True:
cur = sum(g[i][p[i]] for i in range(m))
ans = max(ans, cur)
if not Helper.nextPermutation(p):
break
return ans