Optimal Solution - Programming Theory

Question

I would like someone to explain different approaches to a simple problem and then I am going to try and implement it in PHP for a wider application.

I have five people who are choosing who gets what room in there are five rooms Grand, Large, Medium, Medium and Small.

Person 1 orders the rooms Grand, Large
Person 2 orders the rooms Large, Medium
Person 3 orders the rooms Large, Small
Person 4 orders the room Medium
Person 5 orders the rooms Large, Medium

Where a missing room is one they are not interested in.

What is the fairest way to choose who gets each room?

Answer 1

Fairness is not always well defined.

However, in this case it seems that a person can either get a room he requests, or not. Thus, one can make a strong argument that all solutions where the same number of people get a room they want are equally fair, and solutions where more people get a room they want are more fair than those where fewer get what they want (we are thus not giving any one person preference).

In your example there appears to be only one solution where everyone gets a room he wants. Thus, that is the 'fairest' solution.

The algorithm to find this isjust a depth-first-search (or, branch-and-bound if you need the speedup) that considers all possible allocations and finds a maximal one.

Answer 2

Use a heuristic to compute the matching value of every situation. E.g. if a person remains without a room, the value would be low or negative. If every person remains with the biggest room they ordered, the value would be the highest.

Compute this value for every situation and then take the situation with the highest value.