Известный алгоритм для эффективного распределения элементов и удовлетворения минимумов?

Question

Известный алгоритм для эффективного распределения элементов и удовлетворения минимумов?

Для следующей проблемы мне интересно, существует ли уже известный алгоритм, поскольку я не хочу изобретать велосипед.

В данном случае речь идет о гостиничных номерах, но я думаю, что это не имеет значения:

name   | max guests | min guests
1p     | 1          | 1
2p     | 2          | 2
3p     | 3          | 2
4p     | 4          | 3

Я пытаюсь распределить определенное количество гостей по доступным номерам, но распределение должно соответствовать критерию «минимальное количество гостей» комнаты. Также помещения нужно использовать максимально эффективно.

Возьмем, к примеру, 7 гостей. Я бы не хотел эту комбинацию:

3 x 3p ( 1 x 3 guests, 2 x 2 guests )

.. это удовлетворяет минимальным критериям, но было бы неэффективно. Скорее я ищу такие комбинации, как:

1 x 3p and 1 x 4p
3 x 2p and 1 x 1p
etc...

Я думаю, что это знакомая проблема. Есть ли уже известный алгоритм для решения этой проблемы?

Чтобы уточнить:
Под эффективным я подразумеваю, распределяйте гостей таким образом, чтобы комнаты были заполнены как можно больше (предпочтения гостей равны второстепенная проблема здесь и не важна для алгоритма, который я ищу).
Я хочу, чтобы все перестановки удовлетворяли этому критерию эффективности. Таким образом, в приведенном выше примере 7 x 1p также подойдет.

Итак, вкратце:
Существует ли известный алгоритм, который может максимально эффективно распределять элементы по слотам с минимальной и максимальной емкостью? , всегда удовлетворяет критерию min и пытается максимально удовлетворить критерию max .

10

algorithm sorting language-agnostic

задан Decent Dabbler 24 November 2019 в 15:25

2 ответа

Другие вопросы по тегам:

algorithm sorting language-agnostic

Похожие вопросы:

score 0 · Answer 1

Это может быть сделано как довольно простая модификация рекурсивного алгоритма для перечисления целочисленных разделов. В Python:

import collections

RoomType = collections.namedtuple("RoomType", ("name", "max_guests", "min_guests"))


def room_combinations(count, room_types, partial_combo=()):
    if count == 0:
        yield partial_combo
    elif room_types and count > 0:
        room = room_types[0]
        for guests in range(room.min_guests, room.max_guests + 1):
            yield from room_combinations(
                count - guests, room_types, partial_combo + ((room.name, guests),)
            )
        yield from room_combinations(count, room_types[1:], partial_combo)


for combo in room_combinations(
    7,
    [
        RoomType("1p", 1, 1),
        RoomType("2p", 2, 2),
        RoomType("3p", 3, 2),
        RoomType("4p", 4, 3),
    ],
):
    print(combo)

score 0 · Answer 2

мы должны выбрать список комнаты (возможно, больше чем в один раз для каждой комнаты) способом, что сумма минимального значения выбранной комнаты становится равной или меньшей, чем число гостей и сумма макс. значения становятся равными или больше, чем число гостей.
я определил стоимость как общее свободное пространство в выбранных комнатах. (стоимость = макс. - минута)
Мы можем проверить на ответ с этим кодом и найти все возможные комбинации с минимальной стоимостью. (c# код)

    class FindRooms
    {
        // input
        int numberOfGuest = 7; // your goal
        List<Room> rooms;

        // output
        int cost = -1; // total free space in rooms. 
        List<String> options; // list of possible combinations for the best cost

        private void solve()
        {
            // fill rooms data
            // fill numberOfGuest
            // run this function to find the answer
            addMoreRoom("", 0, 0);
            // cost and options are ready to use
        }

        // this function add room to the list recursively

        private void addMoreRoom(String selectedRooms, int minPerson, int maxPerson)
        {
            // check is it acceptable
            if (minPerson <= numberOfGuest && maxPerson >= numberOfGuest)
            {
                // check is it better than or equal to previous result
                if(maxPerson - minPerson == cost)
                {
                    options.Add(selectedRooms);
                }
                else if (maxPerson - minPerson < cost)
                {
                    cost = maxPerson - minPerson;
                    options.Clear();
                    options.Add(selectedRooms);
                }
            }

            // check if too many room selected
            if (minPerson > numberOfGuest)
                return;

            // add more room recursively
            foreach (Room room in rooms)
            {
                // add room and min and max space to current state and check
                addMoreRoom(selectedRooms + "," + room, minPerson + room.min, maxPerson + room.max);
            }
        }
        public class Room
        {
            public String name;
            public int min;
            public int max;
        }
    }