特定分組算法

Question

我正在編寫一個程序，以形成輔導組，給予學生和導師的可用性。可用性以字母表示的阻塞時間列表給出。例如，如果一個學生的可用性爲[A，C，D]，則他在一天的第一，第三和第四小時內可用。你如何製作一個能夠列出學生名單和輔導員名單的函數，並給出一組最大限度地增加一組學生人數的小組列表？我在Java中工作，但我比算法本身更關心算法。一些更多細節：

團體必須包含3-6名學生和1個導師。

學生只能在一個組中。

學生滿意的數量（放置在一個組中）必須最大化。 例如，假設我們有1-6名學生和兩位導師，這兩位導師都可以在時間A和B上學習。學生可以在1：A，2：A，3：A，4：AB，5：AB，6 ：B中。該算法應返回兩組：[1,2,3，tutor1]和[4,5,6，tutor2]。這將每個學生都分配給某個組，並且最好是說，將1-5放入一個組中並將6放出。

Answer 1

下面是3個想法來幫助你開始。

1. 貪心算法。將列表中的第一個學生與列表中的第一個兼容輔導員進行匹配。將列表中的第二個學生與列表中的第一個兼容輔導員進行匹配。等等。

2. 找到最「熱門」的可用小時，並與該小時首先匹配。然後是最受歡迎等。

3. 查找最少的「熱門」可用小時數，並且首先與該小時匹配。然後，接下來最不受歡迎等

免責聲明：我假設你正在沿着一個學習/愛好/行政便利線的東西，換句話說，有沒有股份了很多錢爲您的項目。如果我的假設是錯誤的，我會建議你需要學習更多關於算法的知識，或者聘請有專長的人。

Answer 2

。你可以把這個問題作爲一個圖形的問題：由一組不相交的子圖的覆蓋，同時尊重兩個分區（學生組）和最大化一個分區的蓋二部圖（學生）

我由此試探m的思維：

• 開始用空的解決方案
• 同時有未分配的學生開放（小於六個成員）組：
  • 排序unass通過免費插槽順序排列的學生
  • 從列表頂部挑選六名學生（從頂部讀取列表，直到您找到六個學生可以參加的組），並將它們用作一個組。
  • 如果你不能挑選六名學生，請選擇最大數量的學生。
  • 如果你不能找到形成三個一組的學生，但你有兩個：
    • 查找當前分配給您可以從（三人以上），一組組第三studend，和用他來填補小組。身高可以從未分配集中
    • 回填如果你不能找到第三人，拿一個來自不同的3名成員組成的組羣。緩慢搜索他在該組中的替代者（或放棄）。您可以嘗試從不同的三個成員組中並行移除。
  • 如果你只有一個學生，看是否可以通過其他兩個人從其他羣體填補他的任何羣體。如果需要，遞歸替換或放棄。
  • 如果你有一個學生，其所有候選組已經滿了，找一個人在任何這些組不能移動到非整組。如果所有替換組已滿，則進行遞歸。
  • 如果你不能找到一個方法來遊移的人，以滿足任何未分配的學生，完成

注意，這歸結爲：

快速找到滿足的解決方案大多數人（你可以在這裏停下來）。然後嘗試找到配對的鏈中插入學生：使用和未使用配對之間

• 交替
• 開始在學生
• 在類結束

注意這是同構在二分圖中找到交替路徑，並且可以如此優化。

請注意，這可能仍然無法找到最佳解決方案，因爲它不會取代單個組中的多個人來滿足某個人。

中的僞上面指示在每一步訴諸學生名單。相反，您可以跟蹤對此列表的更改，並在更新時更新排序順序。

---

更新：我沒有注意到你也想分配教師。

在這種情況下，您需要在指定學生到一個老師分配到組。這將阻止創建一些組，但如果沒有免費的教師，如果您可以爲該組分配不同的教師，則可以從不同組中選擇教師。再次，它只是尋找一個交替的圖形，這次是在教師組子課 - 攪亂學生以釋放一名教師似乎不可行。

，你現在要覆蓋整個圖有三個分區：學生，教師羣體。教師和學生不會互動，所以有兩層：學生組，教師組。這兩個層是獨立的，除了他們必須覆蓋相同的一組組。