The most efficient booking algorithm?

Question

Algorithms

You need to find the cheapest hotel rooms. Let's say 6 people want to check into a hotel. We take a list of free rooms.
In one category, two rooms for two people are available. The cost is 3500. 4 people, 2 rooms = 3500 * 2 = 7000.
In the next category there is a room for 4000. You can accommodate 1 person = 4000.
Then we have a room for 5000, you can also accommodate 1 person there. The total cost is 16,000. I think to solve the problem in the forehead. Take the list of the cheapest rooms multiplied by the number of seats. Then allocate the remaining places to slightly more expensive rooms. Maybe there is some more efficient algorithm to get the lowest possible booking amount? Since I only know the option that I described.

Answer 1

This is in its purest form the task of a backpack (weight is the capacity of the room, in people, and price is the cost). Here it is necessary to dial numbers of exactly given capacity with the lowest cost (in the problem it does not matter at all whether to maximize or minimize the total price).
If we have n people, then we start an array from 0 to n. We note that 0 people can be placed for 0 rubles, and everything else for infinity. Then for each free room () we go through the array from the end to the beginning and, if (current price + room price) for k people is better than the accommodation price (k+room capacity), then we overwrite the best price for k+room capacity. We also save in the auxiliary array what number we have now taken for a given number of people (k + room capacity).
At the end, we look at the cell for n people - there will be a minimum cost.
As a result, the running time of the algorithm is O(n*m), where there are n people and m free rooms.
This dynamic programming solution is even shorter and easier than brute force: literally 2 nested loops to calculate and one while to recover the answer.

Answer 2

It's like a Transport Challenge. Read the description.
In addition, you must specify what you mean by efficiency.
In some cases it may be to make more money.
And in some cases - not to leave a single person uninhabited.
Or just reduce the simple numbers.