LeetCode 1947. 最大兼容性评分和（状态枚举DP）

Michael阿明

发布于 2022-07-31 09:33:23

23300

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录
1. 题目
2. 解题

1. 题目

有一份由 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.length
n == students[i].length == mentors[j].length
1 <= m, n <= 8
students[i][k] 为 0 或 1
mentors[j][k] 为 0 或 1

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/maximum-compatibility-score-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

dp[state] 老师被选择的情况是 state 的二进制位1 表示的状态时的最大得分和

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        n = len(students)
        dp = [0 for _ in range(1<<n)]
        def score(x, y):
            return sum([1 if (xi^yi)==0 else 0 for xi, yi in zip(x, y)])
        # 预处理出来学生和老师的得分
        scores = [[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            for j in range(n):
                scores[i][j] = score(students[i], mentors[j])

		# DP
        for i in range(0, n): # 枚举学生样本
            for state in range(0, 1<<n): # 枚举老师的状态
                if bin(state).count('1') == i: # 老师被选的个数应该为 i 个了
                    for j in range(n):
                        if state&(1<<j) == 0: # j 号 老师还没有被选
                            dp[state|(1<<j)] = max(dp[state] + scores[i][j], dp[state|(1<<j)])
        return dp[-1]

56 ms 14.9 MB Python3

上面是 state 是之前的状态

如果 state 是现在的状态，则代码是

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        n = len(students)
        dp = [0 for _ in range(1<<n)]
        def score(x, y):
            return sum([1 if (xi^yi)==0 else 0 for xi, yi in zip(x, y)])
        # 预处理出来学生和老师的得分
        scores = [[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            for j in range(n):
                scores[i][j] = score(students[i], mentors[j])

		# DP
        for state in range(1, 1<<n): # 枚举老师的状态
            i = bin(state).count('1')  # 老师被选的个数 i 个, 当前学生下标是 i-1
            for j in range(n):
                if state&(1<<j): # 学生 i-1 选择了 j 号 老师
                    dp[state] = max(dp[state^(1<<j)] + scores[i-1][j], dp[state])
        return dp[-1]

我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-30，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法