Most efficient filing

Question

The situation is that i have to fill rooms with a x number of persons. For this example lets use:

$persons = 7;

And i got a array with:

$differentRoom = array(
    'Room 1' => 1, //This room fits 1 person
    'Room 2' => 2, //This room fits 2 persons
    'Room 3' => 3, //This room fits 3 persons
);

Now i want that PHP makes combinations that is exactly 7 in the shortest way. The result have to be, you need : 'Room3' 'Room 3' 'Room 1'

in another example i have

$persons = 15;

And a array with

$differentRooms = array(
    'Room 1' => 4, // This room fits x persons
    'Room 2' => 7,
);

This time a combination can't be exactly 15. In this situation the result have to be a combination that is more then 15. In this case it would be 16. 16 is nearest to 10, and the result have to be. You need : 'Room 2''Room 2' 'Room 1'

How can i do this?

Answer 1

The problem is NP-hard and a variant of the knapsack problem with repetition (http://en.wikipedia.org/wiki/Knapsack_problem for some more info on the subject).

The notable modification is, instead of trying to get the largest weight in as possible, you're trying to get a weight as close as possible to a certain value. This can be done by changing the weight function.

The best solution for it is dynamic programming, which you may want to look into. This, however, is more of an algorithm/CSci question, so it'd be better to post it on the maths/programming stackexchange question boards.