按姓氏将人们分配到不同的房间中？

Question

按姓氏将人们分配到不同的房间中？

16

我经常教授大型入门编程课程（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放在另一个房间中。谢谢！

- templatetypedef

你能否将姓氏首字母相同的学生分配到两个不同的房间里？ - Bill

1

您不需要在单个字母上进行拆分。 - starblue

2

听起来像是一个装箱问题。http://en.m.wikipedia.org/wiki/Bin_packing_problem - Jason Sperske

是否允许环绕（Z->A）？ - nhahtdh

将每个学生分配一个连续的编号会更容易。A房间中的m到n学生，B房间中的o到p学生，依此类推。但那样的话，你就不能花时间编写代码了。 :) - Randy Howard

显示剩余14条评论

4个回答

2

这个问题是NP完全问题，因此对于这个问题没有已知的多项式时间（即高效）解决方案（只要人们不能证明P=NP）。您可以将背包或装箱问题的一个实例减少到您的问题中，以证明它是NP完全问题。

为了解决这个问题，您可以使用0-1背包问题。具体步骤如下：首先选择最大的教室大小，并尝试分配尽可能多的学生组（使用0-1背包），即等于房间的大小。您保证不会分割学生组，因为这是0-1背包。完成后，取下一个最大的教室并继续。（您可以使用任何已知的启发式方法来解决0-1背包问题。）

下面是转化过程：您需要将0-1背包的一般实例减少到特定实例。因此，让我们考虑0-1背包的一般实例。假设有一个重量为W的袋子和您有x1、x2、... xn个组，它们对应的重量为w1、w2、... wn。

现在进行转化——将一般实例转化为您的问题如下：您有一个座位容量为W的教室。每个xi（i∈（1，n））都是一个学生组，其最后一个字母以i开头，其数目（即组的大小）为wi。

现在您可以证明如果0-1背包问题有解，则您的问题就有解……反之亦然。同样，如果0-1背包没有解决方案，则您的问题也没有解决方案，反之亦然。

请记住约简的重要事项——已知NP-C问题的一般实例转化为您问题的特定实例。

希望这有所帮助 :)

- Bill

1

你能解释一下这个约简是如何工作的吗？请记住，为了证明这是NP完全问题，你必须展示如何使用黑盒求解器来解决0-1背包问题，而不是相反。 - templatetypedef

1

你的算法将如何解决A=50，B=100，C=200，D=100和两个容量分别为300和200的教室的问题？注意，你不能随意选择任何一个。 - nhahtdh

1

请记住减少的重要事项——将已知的NP-C问题的一般实例转化为您问题的特定实例。-- 来自我的回答...并更新了第一段，我之前搞反了。感谢指出。 - Bill

1

@Bill：这是错误的。因为A和D不是连续的。请检查问题。 - nhahtdh

2

@Bill：连续的字母块 - 请再次检查问题。它必须是A-D或B-C，如果你在中间拿出一些东西，它就不再是连续的了。 - nhahtdh

显示剩余19条评论

0

这是一种方法，应该在姓氏按首字母分布的常见假设下表现得相当不错。在不牵扯回溯的限制下，尽可能紧凑地从最小容量到最大容量填补房间。

最后将最大的房间列在最后似乎很合理（至少对我来说），因为它是为“其他所有未列出的人”准备的。

- Pieter Geerkens

你将如何确保连续的名称块条件？ - nhahtdh

OP的意图是合理地解决一个真实的问题（即不允许它变成NP问题），还是将一个众所周知的NP问题以稍微不同的形式重新表述？我理解他的意图是（1），而回答者似乎试图将他拖入（2）。只有OP能够提供所需内容的明确解释。 - Pieter Geerkens

换句话说，通过探索一个稍微简单一点的问题，即对于最大容量的房间放松连续名称选择，一个真实世界的解决方案可能更容易编码并且性能更好。 - Pieter Geerkens

从他对我的评论的回复来看，如果有解决方案，他似乎想要一个解决方案。因此，我认为他想要在不牺牲准确性的情况下，在合理的时间内解决问题（而不是一般性的问题），考虑到他所面临的限制条件。有许多问题是NP问题，但对于小规模问题，有比蛮力法更有效的解决方法。 - nhahtdh

我是一名物理学家。在物理学中，人们被教导当问题变得太难时，要探索简化它的方法，以保留其原始精神。 - Pieter Geerkens

0

有必要让生活变得如此复杂吗？为什么不能给每个学生分配注册号码，然后使用该号码来分配他们想要的任何方式呢 :) 您不需要编写代码，学生很高兴，每个人都很开心。

- user2350667

这肯定是可行的，但我对解决这个特定问题感兴趣，因为它提供了一个非常简单的系统，学生可以轻松使用来确定他们的房间号码。没有必要为学生准备一个大表格供他们查看。 - templatetypedef

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SergeyS · Accepted Answer

可以使用某种DP解决方案在[m，2 ^ n]空间上进行解决，其中是字母数（英语为26），是房间数量。当和时，需要约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;
}

以下是问题中的示例：

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

答案将是：

这表示每个学生姓氏字母对应的房间索引。如果无法分配，我的解决方案将返回null。

[编辑]

在成千上万的自动生成测试中，我的朋友发现了一个构建解决方案的代码bug。它不影响主要算法，因此修复此bug将成为读者的练习。

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