題目連結:
題目意譯:
現在有一個問卷調查由 n 個問題組成,其中每個問題的答案只會是 0(no) 或是 1(yes)。
問卷給予了 m 位學生編號 0 到 m - 1 以及 m 位導師編號為 0 到 m - 1。學生的答案以一個二維整數陣列 students 表示,其中 students[i] 為一整數陣列包含著第 i 位學生的答案(索引值從 0 開始)。導師的答案以一個二維整數陣列 mentors 表示,其中 mentors[j] 為一整數陣列包含著第 j 位導師的答案(索引值從 0 開始)
每位學生將會被分配於一位導師,以及每位導師將會有一位學生分配到他們身上。一對學生-導師之相容分數為學生與導師相對應位置之答案相同的數量。
例如,如果學生的答案為 [1, 0, 1] 且導師的答案為 [0, 0, 1],則他們的相容分數為 2 因為第二以及第三位置的答案是相同的。
你被要求找到最佳的學生-導師之組合來最大化所有相容分數的總和。
給定 students 和 mentors,回傳可以達成的最大相容分數之總和。
限制:
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。
範例測資:
範例 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! 種排列。然後利用上面的陣列查詢當前此種排列的分數總和。而所有排列中最大的即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。