Задача такова:

имеются 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 человек

Как расселить туристов?

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

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

см. классическую задачу рюкзака.

Огромное спасибо!

В принципе, единственным значимым отличием данной задачи от задачи о рюкзаке является количество рюкзаков: здесь их K, а в задаче о рюкзаке рюкзак один, что немного усложняет задачу.

Еще раз спасибо, попробую разобраться.

В данный момет, после семичасового поиска в интернете имею следущее:

• задача о рюкзаке (backpack/knapsack problem)
• bin packing problem
• задача о парламенте
• задача о назначениях
• задача о суммах подмножеств (subset-sum problem)
• задачи теории расписаний (задача Джонсона)

Но, разумеется, ни одна из выше указанных задач не подходит под определение "задачи о туристах". Есть сходства, конечно. На мой взгляд болше всех подходит задача о суммах подмножеств. Проблема в том , что задача решает проблему для лишь одного натурального числа, а необходимо решить задачу для n-чисел, при этом состовляя суммы подмножеств из одной и той же группы элементов.

Привожу решение для одного натурального числа:

Цитата

Задача о суммах подмножеств ("табличный" алгоритм) Пусть задана пара (S, t), где S = {x1, x2, …, xn} представляет собой множество положительных целых чисел, а t — положительное целое число. Требуется отыскать среди подмножеств множества S, сумма которых не превосходит t, такое, у которого сумма ближе всего к t. Пусть |S| = n. Обозначим (k, w) — задачу, в которой имеется k первых чисел из S и нужно набрать сумму w. Таким образом исходная задача — это задача (n, t). Для решения задачи построим таблицу T[n, t + 1], в клетку T[i, j] которой будем записывать оптимальное решение задачи (i, j). Первый столбец заполним нулями. Первую строку заполним сначала нулями, а начиная с клетки (1, x1) — числами x1. Клетку T[i, j] (i, j > 1) будем заполнять по правилу: Если j − xi > 0, то y := T[i − 1, j − xi], иначе y := 0; T[i, j] := max(T [i − 1, j], y + xi) \  0 1 2 3 4 5 6 7 8 9 10 11 12 13 3  0 0 0 3 3 3 3 3 3 3  3  3  3  3 5  0 0 0 3 3 5 5 5 8 8  8  8  8  8 7  0 0 0 3 3 5 5 7 8 8 10 10 12 12 9  0 0 0 3 3 5 5 7 8 9 10 10 12 12 11 0 0 0 3 3 5 5 7 8 9 10 11 12 12 S = {3, 5, 7, 9, 11} t = 13; Таблица примет такой вид. Ответ: нет подмножества весом 13, ближе всего снизу 12. Условие (2) говорит о том, что оптимальная сумма может достигаться либо без использования xi (T[i − 1, j]), либо если xi входит в сумму (y + xi). В этом случае его надо прибавить к решению задачи (i − 1, j − xi), что и сохраняется в переменной y в условии (1). Из получившейся таблицы можно узнать и состав оптимальной суммы. Трудоемкость этого алгоритма очевидно составляет O (nt) операций. Таким образом, если t будет велико, можно будет все числа поделить, к примеру, на 10, округлить и получить приближенный алгоритм.

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

Гостиницы - это рюкзаки (у каждого своя вместительность)
Семьи туристов - это вещи, которые мы кладем в рюкзаки (у каждой вещи свой объём)
объем, как параметер, я беру лишь для ясности, так как понятие вместительности рюкзака легче связать с вместительностю гостиниц - на самом деле правельнее было взять вес

Ограничение таково:

если рюкзак i может вместить Vi объём, то необходимо найти такие вещи, сумма объемов которых S точно равна Vi:
Vi=S,
иначе, если рюкзак i может вместить минимум Vi1 объёма, а максимум Vi2 объёма, то найти такие вещи, сумма объемов которых не меньше Vi1, но не превышает Vi2:
Vi1 <= S <= Vi2.

У кого-нибудь есть идеи как решаеться задача о нескольких рюкзаках (хотя бы без этого ограничения)?

Правильно. В целевую функцию просто добавится еще одна сумма (по количеству "рюкзаков") + ограничения.
Применяй методы целочисленного линейного програмимрования. Тут количество рюкзаков не так важно, методология та же, что для большинства целочисленных задач комбинаторного типа.

Последнее ограничение-неравенство справедливо именно в таком виде, если ставится условие, что в одну гостиницу обязательно должен быть хоть кто-то поселен.