它可以在空间上使用某种 DP 解决方案来解决[m, 2^n]，其中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。
[编辑]
经过数千次自动生成的测试后，我的朋友在代码中发现了一个向后构建解决方案的错误。它不会影响主要算法，因此修复此错误将是读者的练习。
揭示错误的测试用例是students = [13,75,21,49,3,12,27,7]和rooms = [6,82,89,6,56]。我的解决方案没有返回任何答案，但实际上有一个答案。请注意，解决方案的第一部分工作正常，但答案构造部分失败。