Оптимальное соответствие
Задача такова:
имеются N туристов и K гостиниц. Необходимо разместить всех туристов в гостиницах.
Ограничения:
- туристы состоят из семей. Семья может состоять из одного или более человек.
- каждая гостиница имеет минимум и максимум вместительности (минимум означает, что хозяин гостиницы не согласен поселить меньше минимума)
- одна отдельно взятая семья обязана быть поселена в одну гостиницу
Также дано:
- общее количество свободных мест в гостиницах больше или равно количеству туристов
- всего M семей
Пример:
туристы: 1, 1, 1, 1, 1, 1, 4, 1, 1, 7, 1, 2, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 5, 2, 1, 1, 2
свободные места в гостиницах: [10], [2..6], [5..10], [11], [8], [12..17], [4], [1], [2] ,[1]
[10] - хозяин гостиницы согласен поселить у себя только 10 человек (не меньше и не больше)
[2..6] - хозяин гостиницы согласен поселить у себя от 2 до 6 человек
Как расселить туристов?
Разумееться речь идет об алгоритме, который потом можно будет применить на практике.
Если это уже известная проблема, то это, конечно, прекрасно. Если нет, подскажите как подобную проблему можно решить.
Заранее благодарен за любую помошь.
имеются N туристов и K гостиниц. Необходимо разместить всех туристов в гостиницах.
Ограничения:
- туристы состоят из семей. Семья может состоять из одного или более человек.
- каждая гостиница имеет минимум и максимум вместительности (минимум означает, что хозяин гостиницы не согласен поселить меньше минимума)
- одна отдельно взятая семья обязана быть поселена в одну гостиницу
Также дано:
- общее количество свободных мест в гостиницах больше или равно количеству туристов
- всего M семей
Пример:
туристы: 1, 1, 1, 1, 1, 1, 4, 1, 1, 7, 1, 2, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 5, 2, 1, 1, 2
свободные места в гостиницах: [10], [2..6], [5..10], [11], [8], [12..17], [4], [1], [2] ,[1]
[10] - хозяин гостиницы согласен поселить у себя только 10 человек (не меньше и не больше)
[2..6] - хозяин гостиницы согласен поселить у себя от 2 до 6 человек
Как расселить туристов?
Разумееться речь идет об алгоритме, который потом можно будет применить на практике.
Если это уже известная проблема, то это, конечно, прекрасно. Если нет, подскажите как подобную проблему можно решить.
Заранее благодарен за любую помошь.
Цитата:
Originally posted by strlen
Задача такова:
имеются N туристов и K гостиниц. Необходимо разместить всех туристов в гостиницах.
Ограничения:
- туристы состоят из семей. Семья может состоять из одного или более человек.
- каждая гостиница имеет минимум и максимум вместительности (минимум означает, что хозяин гостиницы не согласен поселить меньше минимума)
- одна отдельно взятая семья обязана быть поселена в одну гостиницу
Также дано:
- общее количество свободных мест в гостиницах больше или равно количеству туристов
- всего M семей
Пример:
туристы: 1, 1, 1, 1, 1, 1, 4, 1, 1, 7, 1, 2, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 5, 2, 1, 1, 2
свободные места в корпусах: [10], [2..6], [5..10], [11], [8], [12..17], [4], [1], [2] ,[1]
[10] - хозяин гостиницы согласен поселить у себя только 10 человек (не меньше и не больше)
[2..6] - хозяин гостиницы согласен поселить у себя от 2 до 6 человек
Как расселить туристов?
Разумееться речь идет об алгоритме, который потом можно будет применить на практике.
Если это уже известная проблема, то это, конечно, прекрасно. Если нет, подскажите как подобную проблему можно решить.
Заранее благодарен за любую помошь.
Задача такова:
имеются N туристов и K гостиниц. Необходимо разместить всех туристов в гостиницах.
Ограничения:
- туристы состоят из семей. Семья может состоять из одного или более человек.
- каждая гостиница имеет минимум и максимум вместительности (минимум означает, что хозяин гостиницы не согласен поселить меньше минимума)
- одна отдельно взятая семья обязана быть поселена в одну гостиницу
Также дано:
- общее количество свободных мест в гостиницах больше или равно количеству туристов
- всего M семей
Пример:
туристы: 1, 1, 1, 1, 1, 1, 4, 1, 1, 7, 1, 2, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 5, 2, 1, 1, 2
свободные места в корпусах: [10], [2..6], [5..10], [11], [8], [12..17], [4], [1], [2] ,[1]
[10] - хозяин гостиницы согласен поселить у себя только 10 человек (не меньше и не больше)
[2..6] - хозяин гостиницы согласен поселить у себя от 2 до 6 человек
Как расселить туристов?
Разумееться речь идет об алгоритме, который потом можно будет применить на практике.
Если это уже известная проблема, то это, конечно, прекрасно. Если нет, подскажите как подобную проблему можно решить.
Заранее благодарен за любую помошь.
Переборчик, возвратный алгоритм и т.д.
Цитата:
Originally posted by wanja
Переборчик, возвратный алгоритм и т.д.
Переборчик, возвратный алгоритм и т.д.
Кроме этого, сперва нужно бы вычеркнуть те гостинницы и группы, которые "соответствуют" друг другу. Т.е. группа состоит из 4 человек и в гостиннице 4 свободных мест.
И нужно бы упорядочить гостинницы и группы в порядке убывания численности.
Спасибо за ответы.
После нескольких дней проведенных (в интернете) за поиском подобных задач, честно говоря, я не ожидал узнать, что очень много известных задач и проблем, хоть и косвенно, но связаны с этой проблемой: начиная от задачи о рюкзаке и заканчивая задачей о назначениях.
Есть также более простая задача о суммах подмножеств - без нее вообще никуда.
Только как это все объеденить воедино и решить данную задачу?
Может кто поможет с общим алгоритмом? На чем основываеться последовательность выбора, например?
После нескольких дней проведенных (в интернете) за поиском подобных задач, честно говоря, я не ожидал узнать, что очень много известных задач и проблем, хоть и косвенно, но связаны с этой проблемой: начиная от задачи о рюкзаке и заканчивая задачей о назначениях.
Есть также более простая задача о суммах подмножеств - без нее вообще никуда.
Только как это все объеденить воедино и решить данную задачу?
Может кто поможет с общим алгоритмом? На чем основываеться последовательность выбора, например?
Люди, кто-то знает как решается задача о нескольких рюкзаках?