用于有效分配项目和满足最小值的已知算法？

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

对于 efficint = 使用的最少房间，也许这会起作用。为了最大限度地减少使用的房间数量，您需要将其放置max guests在大房间中。

因此，按降序对房间进行排序max guests，然后按顺序分配客人，max guests依次放入每个房间。尝试将所有剩余的客人安排在任何可以容纳这么多客人的剩余房间中min guests；如果不可能，请返回并重试。回溯时，保留最小的房间min guests。保留房间不分配客人的阶段max guests。

编辑

正如瑞奇·鲍比（Ricky Bobby）指出的那样，由于回溯的困难，这并不奏效。我暂时保留这个答案，更多的是作为警告而不是建议:-)