Разделение людей в комнаты по фамилии?

Ответ 1

Его можно решить с помощью своего рода решения DP на [m, 2^n] пространстве, где m - количество букв (26 для английского), а n - количество комнат. При m == 26 и n == 20 это займет около 100 МБ пространства и ~ 1 с времени. Ниже приведено решение, которое я только что реализовал в С# (он будет успешно компилироваться на С++ и 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]. Мое решение не отвечает, но на самом деле есть ответ. Обратите внимание, что первая часть решения работает правильно, но ответ на конструктивную часть не выполняется.

Ответ 2

Эта проблема NP-Complete и, следовательно, для этого нет известного polynomial времени (ака эффективного) решения (пока люди не могут доказать P = NP). Вы можете уменьшить экземпляр проблемы с рюкзаком или бин-упаковкой, чтобы доказать, что это NP-Complete.

Чтобы решить эту проблему, вы можете использовать проблему с рюкзаком 0-1. Вот как это сделать: Сначала выберите самый большой классный класс и постарайтесь выделить столько групп студентов, которые вы можете (используя рюкзак 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, ваша проблема имеет решение... и обратное.... также если нет решения для рюкзака 0-1, то ваша проблема имеет нет решения, и наоборот.

Пожалуйста, помните важную вещь сокращения - общий пример известной проблемы NP-C для конкретного экземпляра вашей проблемы.

Надеюсь, что это поможет:)

Ответ 3

Вот подход, который должен работать достаточно хорошо, учитывая общие предположения о распределении фамилий по инициативе. Заполните комнаты от наименьшей емкости до максимально компактной, насколько это возможно, в пределах ограничений, без возврата.

Мне кажется разумным (по крайней мере, для меня), потому что самая большая комната должна быть указана последним, поскольку для "всех остальных" еще не указано.

Ответ 4

Есть ли причина сделать жизнь такой сложной? Почему вы не можете назначать регистрационные номера каждому учащемуся, а затем использовать номер, чтобы распределять их так, как вы хотите:) Вам не нужно писать код, студенты довольны, все довольны.