- #1

CompuChip

Science Advisor

Homework Helper

- 4,302

- 47

Hey guys,

Here is an interesting problem that I find to be a lot harder to solve than I initially thought.

Suppose you are a hotel manager and people keep asking you to make an offer to their groups. You want to make a simplified model that does the following:

- The group size is given:

- You have room types

- There may be different room types i, j for which

- The number of rooms of each type is unlimited

For now I will be satisfied to solve this problem without additional constraints (like the price of the room).

Do you know of some nice algorithm which will tell me how many rooms

- all

- the number of rooms is minimal (i.e. if there is a room with

- the number of empty beds is minimal (i.e. if

[edit]Solutions may be greedy, as the number of room types will be fairly small (usually 1 to 5) as will the number of people

Here is an interesting problem that I find to be a lot harder to solve than I initially thought.

Suppose you are a hotel manager and people keep asking you to make an offer to their groups. You want to make a simplified model that does the following:

- The group size is given:

*n*adults- You have room types

*i*, which can accommodate between*a*_{i}and*b*_{i}people ([itex]0 < a_i \le b_i[/itex])- There may be different room types i, j for which

*a*_{i}=*a*_{j}and*b*_{i}=*b*_{j}, then just choose one (e.g. the one with lowest*i*).- The number of rooms of each type is unlimited

For now I will be satisfied to solve this problem without additional constraints (like the price of the room).

Do you know of some nice algorithm which will tell me how many rooms

*r*_{i}of type*i*the manager should reserve, such that- all

*n*persons have a bed, i.e. [tex]\sum_i r_i b_i \le n[/tex]- the number of rooms is minimal (i.e. if there is a room with

*a*_{i}=*b*_{i}= 1 then taking that room*n*times is a possible but not a preferred solution)- the number of empty beds is minimal (i.e. if

*n*= 1 and there is a room with*a*_{i}= 1,*b*_{i}= 6, then one room of that type will do but it is not preferred because 5 beds will be empty).[edit]Solutions may be greedy, as the number of room types will be fairly small (usually 1 to 5) as will the number of people

*n*(usually 1 to 4); but the algorithm should be as fast as possible of course, having to be run rather often[/edit]
Last edited: