按姓氏將人分爲房間？

Question

我經常教大型的入門級編程課程（400-600名學生），考試時間到了，我們經常不得不把課程分成不同的房間，以確保每個人都有考試席位。

爲了保持物流的簡單性，我通常會用姓將課程分開。例如，我可能會把學生姓名A - H送到一個房間，姓I - L給第二個房間，M - S給第三個房間，而T - Z送到第四個房間。

這樣做的挑戰在於，房間的容量常常大不相同，而且很難找到一種方法來分類課程，使得每個人都適合。例如，假設姓氏的分佈（爲簡單起見）以下：

• 姓開始使用A：25
• 姓與B開始：150
• 姓以C開頭： 200
• 姓與d開始：50

假設我有配備了容量350，50，和50貪婪算法查找房間分配可能是房間整理到容量的降序排列，然後嘗試按照該順序填寫房間。不幸的是，這並不總是奏效。例如，在這種情況下，正確的選擇是將姓A放入一個大小爲50的房間，姓名B-C放入大小爲350的房間，姓D放入另一個大小爲50的房間。貪婪算法會把姓名A和B放入350人的房間，然後找不到其他人的座位。

只需嘗試房間排序的所有可能排列，然後在每個排序上運行貪婪算法，就很容易解決此問題。這可以找到一個可以工作的任務或報告沒有任何任務。但是，我想知道是否有更有效的方法來實現這一點，因爲房間的數量可能在10到20之間，檢查所有的排列可能是不可行的。

總之，正規的問題陳述如下：

你給了學生們的姓氏的頻率直方圖中的一類，與房間和能力的名單。您的目標是通過姓氏的第一個字母來分配學生，以便爲每個房間分配一個連續的字母塊並且不超過其容量。

是否有一個有效的算法，或者至少有一個高效的合理房間大小？

編輯：很多人都問過這個連續的條件。規則是

• 每間客房都應當在大多數被分配連續的字母塊，並
• 沒有字母應該分配到兩個或多個房間。

例如，您不能將A - E，H - N和P - Z放入同一個房間。你也不能把A-C放在一個房間裏，B-D放在另一個房間裏。

謝謝！

Answer 1

這個問題是NP-Complete因此沒有已知的polynomial時間（aka效率）解決方案（只要人們不能證明P = NP）。您可以減少揹包或垃圾箱問題的實例，以證明您的問題是NP-complete。

要解決這個問題，你可以使用0-1揹包問題。這裏是： 首先選擇最大的教室大小，並嘗試分配儘可能多的學生組（使用0-1揹包），即等於房間的大小。你保證不會分裂一羣學生，因爲這是0-1揹包。一旦完成，請繼續下一個最大的教室。

（您可以使用任何已知的啓發式解決揹包問題。）

這裏是降低 - 你需要0-1揹包的一般情況下降低您的問題的一個具體實例。 所以我們來看一個0-1揹包的一般實例。讓我們拿一個袋子，它的重量是W，你有x_1, x_2, ... x_n組，它們相應的權重是w_1, w_2, ... w_n。

現在減少---這個一般情況減少到你的問題如下： 你有一個教室，座位容量爲W。每個x_i (i \in (1,n))是一組學生，其最後一個字母以i開頭，他們的數字（又稱組的大小）爲w_i。

現在你可以證明是否存在0-1揹包問題的解決方案，你的問題有一個解決方案...和converse ....如果沒有解決方案0-1揹包，那麼你的問題沒有解決辦法，反之亦然。

請記住減少的重要事項 - 針對您問題的特定實例的已知NP-C問題的一般情況。

希望這有助於:)使用某種形式的解決方案DP上[m, 2^n]空間，其中m是字母數字（26英語）和n是客房數量

Answer 2

它是可以解決的。使用m == 26和n == 20它將需要大約100 MB的空間和〜1秒的時間。 下面是解決方案，我剛纔在C＃實現的（它會成功編譯的C++和Java也將需要只是一些小的改動）：

int[] GetAssignments(int[] studentsPerLetter, int[] rooms) 
{ 
    int numberOfRooms = rooms.Length; 
    int numberOfLetters = studentsPerLetter.Length; 
    int roomSets = 1 << numberOfRooms; // 2^(number of rooms) 
    int[,] map = new int[numberOfLetters + 1, roomSets]; 

    for (int i = 0; i <= numberOfLetters; i++) 
     for (int j = 0; j < roomSets; j++) 
      map[i, j] = -2; 

    map[0, 0] = -1; // starting condition 

    for (int i = 0; i < numberOfLetters; i++) 
     for (int j = 0; j < roomSets; j++) 
      if (map[i, j] > -2) 
      { 
       for (int k = 0; k < numberOfRooms; k++) 
        if ((j & (1 << k)) == 0) 
        { 
         // this room is empty yet. 
         int roomCapacity = rooms[k]; 
         int t = i; 
         for (; t < numberOfLetters && roomCapacity >= studentsPerLetter[t]; t++) 
          roomCapacity -= studentsPerLetter[t]; 

         // marking next state as good, also specifying index of just occupied room 
         // - it will help to construct solution backwards. 
         map[t, j | (1 << k)] = k; 
        } 
      } 

    // Constructing solution. 
    int[] res = new int[numberOfLetters]; 
    int lastIndex = numberOfLetters - 1; 
    for (int j = 0; j < roomSets; j++) 
    { 
     int roomMask = j; 
     while (map[lastIndex + 1, roomMask] > -1) 
     { 
      int lastRoom = map[lastIndex + 1, roomMask]; 
      int roomCapacity = rooms[lastRoom]; 
      for (; lastIndex >= 0 && roomCapacity >= studentsPerLetter[lastIndex]; lastIndex--) 
      { 
       res[lastIndex] = lastRoom; 
       roomCapacity -= studentsPerLetter[lastIndex]; 
      } 

      roomMask ^= 1 << lastRoom; // Remove last room from set. 

      j = roomSets; // Over outer loop. 
     } 
    } 

    return lastIndex > -1 ? null : res; 
} 

來自實例OP問題：

int[] studentsPerLetter = { 25, 150, 200, 50 }; 
int[] rooms = { 350, 50, 50 }; 
int[] ans = GetAssignments(studentsPerLetter, rooms); 

答案是：

2 
0 
0 
1 

指示的空間爲每個學生的姓氏字母索引。如果分配不可行，我的解決方案將返回null。

---

[編輯]

經過千自動生成的測試我的朋友已經發現，在代碼向後構建解決方案的錯誤。它不會影響主算法，因此修復這個錯誤將是對讀者的一個練習。

揭示該錯誤的測試用例是students = [13,75,21,49,3,12,27,7]和rooms = [6,82,89,6,56]。我的解決方案沒有回答，但實際上有一個答案。請注意，解決方案的第一部分正常工作，但回答構造部分失敗。

Answer 3

這是一個應該工作得相當好的方法，假設通過初始分配姓氏的常見假設。在約束範圍內儘可能緊湊地填充房間從最小容量到最大容量，無需回溯。

對於最後列出的最大房間而言，對於「其他人」尚未列出的似乎是合理的（至少對我而言）。

Answer 4

有什麼理由讓生活如此複雜？爲什麼你不能給每個學生分配註冊號碼，然後用你想要的方式分配註冊號碼:)你不需要編寫代碼，學生很開心，每個人都很開心。