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

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, , всегда удовлетворяющими критериям min и , пытающимся удовлетворить max критерий как можно больше.

Answer 1

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

Ваша функция стоимости может быть чем-токак:

Сумма вакансий в комнатах + количество комнат

---

Это может быть немного похоже на проблему с наименьшей резкостью: Перенос слов в X строк вместо максимальной ширины(Наименьшая грубость)

Вы подходите людям в комнате, как вы подбираете слова в строке.

Ограничениями являются вакансии в комнатах, а не длина линий.(бесконечные затраты, если вы не выполните все ограничения)

и отношение рекурсии почти такое же.

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

Answer 2

$sql = "SELECT * 
FROM rooms 
WHERE min_guests <= [$num_of_guests]
ORDER BY max_guests DESC
LIMIT [$num_of_guests]";

$query = $this->db->query($sql);
$remaining_guests = $num_of_guests;
$rooms = array();
$filled= false;
foreach($query->result() as $row)
{
 if(!$filled)
 {
  $rooms[] = $row;
  $remaining_guests -= $row->max_guests;
  if(remaining_guests <= 0)
  {
   $filled = true;
   break;
  }
 }
}

Рекурсивная функция:

public function getRoomsForNumberOfGuests($number)
{
  $sql = "SELECT * 
  FROM rooms 
  WHERE min_guests <= $number
  ORDER BY max_guests DESC
  LIMIT 1";

  $query = $this->db->query($sql);
  $remaining_guests = $number;
  $rooms = array();
  foreach($query->result() as $row)
  {
    $rooms[] = $row;
    $remaining_guests -= $row->max_guests;
    if($remaining_guests > 0)
    {
     $rooms = array_merge($this->getRoomsForNumberOfGuests($remaining_guests), $rooms);
    }
  }
  return $rooms;
}

Будет ли что-то подобное для тебя? Не уверены, на каком языке вы говорите?

Answer 3

Для эффективности = минимальное количество используемых комнат, возможно, это будет работать.Чтобы свести к минимуму количество используемых комнат, вы хотите поместить max guests в большие комнаты.

Сортируйте комнаты в порядке убывания max guests, а затем распределите гостей по ним в таком порядке, разместив max guestsв каждой комнате по очереди.Постарайтесь разместить всех оставшихся гостей в любой оставшейся комнате, которая примет столько min guests;если это невозможно, вернитесь назад и попробуйте снова.При обратном слежении удерживайте комнату с наименьшим значением min guests.В зарезервированных комнатах не размещаются гости на этапе max guests.

---

РЕДАКТИРОВАТЬ

Как указал Рики Бобби , это делаетне работать как таковой, из-за сложности обратного отслеживания.Я пока держу этот ответ, скорее как предупреждение, чем как предложение: -)