algorithm - 按姓氏将人们分配到房间？

Question

我经常教授大型入门编程类(class)(400 - 600 名学生)，当考试时间临近时，我们通常不得不将类(class)分成不同的房间，以确保每个人都有座位参加考试。

为了在逻辑上保持简单，我通常按姓氏将类(class)分开。例如，我可能会将姓氏 A - H 的学生送到一个房间，将姓氏 I - L 送到第二个房间，将姓氏 M - S 送到第三个房间，将姓氏 T - Z 送到第四个房间。

这样做的挑战在于，房间的容纳人数通常大相径庭，而且很难找到一种让每个人都能适应的方式来划分类(class)。例如，假设姓氏的分布(为简单起见)如下:

• 姓氏以 A 开头:25
• 姓氏以 B 开头:150
• 姓氏以 C 开头:200
• 姓氏以 D 开头:50

假设我有容量为 350、50 和 50 的房间。用于查找房间分配的贪婪算法可能是将房间按容量降序排列，然后尝试按该顺序填充房间。不幸的是，这并不总是有效。例如，在这种情况下，正确的选择是将姓氏 A 放入一个大小为 50 的房间，将姓氏 B - C 放入大小为 350 的房间，将姓氏 D 放入另一个大小为 50 的房间。贪心算法将将姓氏 A 和 B 放入 350 人的房间，然后无法为其他人找到座位。

只需尝试房间排序的所有可能排列，然后对每个排序运行贪心算法，即可轻松解决此问题。这将找到有效的分配或报告不存在。但是，考虑到房间数量可能在 10 到 20 之间并且检查所有排列可能不可行，我想知道是否有更有效的方法来执行此操作。

总而言之，正式的问题陈述如下:

You are given a frequency histogram of the last names of the students in a class, along with a list of rooms and their capacities. Your goal is to divvy up the students by the first letter of their last name so that each room is assigned a contiguous block of letters and does not exceed its capacity.

是否有一个有效的算法，或者至少有一个对合理的房间大小有效的算法？

编辑:很多人都问过连续条件。规则是

• 每个房间最多应分配一 block 连续的字母，并且
• 不应将任何字母分配给两个或多个房间。

例如，您不能将 A - E、H - N 和 P - Z 放入同一个房间。您也不能将 A - C 放在一个房间，而将 B - D 放在另一个房间。

谢谢!

Answer 1

可以在 [m, 2^n] 空间上使用某种 DP 解决方案来解决，其中 m 是字母数(英语为 26)并且 n 是房间数。使用 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。

---

[编辑]

经过数千次自动生成的测试后，我的 friend 在代码中发现了一个向后构造解决方案的错误。它不影响主要算法，因此修复此错误将成为读者的练习。

揭示错误的测试用例是 students = [13,75,21,49,3,12,27,7] 和 rooms = [6,82,89, 6,56]。我的解决方案没有返回任何答案，但实际上有一个答案。请注意，解决方案的第一部分工作正常，但答案构建部分失败。