A well-known algorithm for efficiently distributing items and meeting lows?

Question

For the next problem, I wonder if an already known algorithm exists, since I don't want to reinvent the wheel.

In this case, this applies to hotel rooms, but I think it does not matter:

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

I am trying to distribute a certain number of guests according to the available rooms, but the distribution should satisfy the criteria of "minimum guests" in the rooms. In addition, the rooms must be used as efficiently as possible.

Let them take, for example, 7 guests. I would not want this combination:

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

.. this will meet the minimum criteria, but will be ineffective. Rather, I am looking for combinations such as:

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

I would think this is a familiar problem. Is there any known algorithm to solve this problem?

To clarify:
Effectively, I mean distributing the guests in such a way that the rooms are filled as much as possible (the preferences of the guests here are secondary and not important for the algorithm I'm looking for).
I do want all permutations that satisfy these performance criteria. So in the above example, 7 x 1p would also be fine.

So, in the summary:
Is there a well-known algorithm that can efficiently distribute elements among slots with a capacity of min and max that always satisfy the criteria of min and try to satisfy max as much as possible.

Answer 1

You need to use dynamic programming , define a cost function and try to put people in possible rooms with the lowest cost possible.

Your cost function might be something like this:

Sum of vacancies in rooms + number of rooms

---

This might be a bit like the least difficult problem: Wrap words in X strings instead of maximum width (smallest evenness)

You fit the people in the room because you match the words in the queue.

Restrictions are vacancies in rooms, not the length of lines. (infinite cost if you do not fill the limits)

and the recursion ratio is almost the same.

Hope this helps

Answer 2

For efficiency = minimum used rooms, maybe this will work. To minimize the number of rooms used, you want to place max guests in large rooms.

So, sort the rooms in descending order by max guests , then arrange them in that order by placing max guests in each room in turn. Try to place all the remaining guests in any remaining room that will host many min guests ; if this is not possible, go back and try again. When tracking backwards, hold the room with the smallest min guests . In the rear rooms, guests in the max guests phase are not allocated.

---

EDIT

As Ricky Bobby pointed out, this does not work as such due to the difficulty of tracking backwards. I keep this answer for now, more like a warning than a suggestion :-)

Answer 3

 $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; } } } 

Recursive function:

 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; } 

Something like this work for you? Not sure which language you are in?