1947. 最大兼容性评分和Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

有一份由 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

# 思路

状压DP，二维的写法很好理解，f[i][j]，i 表示对第 i 个学生进行匹配，j 表示老师的匹配状态，则转移方程为：

f[i][j] = Math.max(f[i][j], f[i - 1][j ^ (1 << k)] + cnt[i][k + 1])

# 解法

// 3ms
class Solution {
    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
        int m = students.length, mask = 1 << m;
        int[][] cnt = new int[m + 1][m + 1], f = new int[m + 1][mask];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                cnt[i + 1][j + 1] = getScore(students[i], mentors[j]);
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j < mask; j++) {
                for (int k = 0; k < m; k++) {
                    if ((j & (1 << k)) != 0) {
                        f[i][j] = Math.max(f[i][j], f[i - 1][j ^ (1 << k)] + cnt[i][k + 1]);
                    }
                }
            }
        }
        return f[m][mask - 1];
    }

    int getScore(int[] a, int[] b) {
        int res = 0;
        for (int i = 0; i < a.length; i++) {
            res += a[i] == b[i] ? 1 : 0;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 总结

分析出几种情况，然后分别对各个情况实现

#Java