Known algorithm for efficiently distributing items and satisfying minima?

Question

For the following problem I'm wondering if there is a known algorithm already as I don't want to reinvent the wheel.

In this case it's about hotel rooms, but I think that is rather irrelevant:

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

I'm trying to distribute a certain amount of guests over available rooms, but the distribution has to satisfy the 'min guests' criteria of the rooms. Also, the rooms need to be used as efficiently as possible.

Let's take 7 guests for example. I wouldn't want this combination:

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

.. this would satisfy the minimum criteria, but would be inefficient. Rather I'm 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 already to solve this problem?

To clarify:
By efficient I mean, distribute guests in such a way that rooms are filled up as much as possible (guests preferences are of secondary concern here, and are not important for the algorithm I'm looking for).
I do want all permutations that satisfy this efficiency criteria though. So in above example 7 x 1p would be fine as well.

So in summary:
Is there a known algorithm that is able to distribute items as efficiently as possible over slots with a min and max capacity, always satisfying the min criteria and trying to satisfy the max criteria as much as possible.

Answer 1

You need to use dynamic programming, define a cost function, and try to fit people in possible rooms having a cost function as small as possible.

Your cost function can be something like :

Sum of vacancy in rooms + number of rooms

---

It can be a bit similar to the least rageness problem : Word wrap to X lines instead of maximum width (Least raggedness)

You fit people in room, as you fit words in line.

The constraints are the vacancies in the rooms instead of being the length of the lines. (infinite cost if you don't fullfil the constraints)

and the recursion relation is pretty much the same .

Hope it helps