Good day,
Please consider the following problem: 3 friends named Alice, Bob and Cindy have 3 food items (cheese, tomato, bread) in the fridge.
Each person has a particular numerical preference score (any positive number) for each food item.
It has been agreed upon that each person should take one and exactly one food item. (cheese bread and tomato can not be broken up to pieces)
we are interested in coming up with a matching that would maximising the total happiness.
Here is a concrete example:
Foods Vector: [Cheese, Tomato, Bread]
preferance vector: (Preference score for Cheese, Tomato and Bread in order)
Alice (4,3,3)
Bob (2,4,5)
Cindy (5,1,3)
brute force: try all combos
//Cheese belongs to Alice, Tomato belongs to Bob, Bread belongs to Cindy...
total score for [Alice,Bob,Cindy]: 11
total score for [Alice,Cindy,Bob]: 8
total score for [Bob,Cindy,Alice]: 6
total score for [Bob,Alice,Cindy]: 8
total score for [Cindy,Bob,Alice]: 12
total score for [Cindy,Alice,Bob]: 13 //best solution
It looks like we should give Cheese to Cindy, Tomato to Alice, and Bread to Bob for the greater good of the republic.
Of course the naive brute force method is acceptable here because n=3, however if we have 100 people and 100 food items this method would be prohibitively expensive. it seems to me that n! will be the asymptotic complexity which is worse than exponential.
I attempted to relate this problem to other well known problems like knapsack or Interval scheduling with no success.
I would appreciate informed input on the type of this problem and if there are other approaches to find the optimal or good approximation solution in reasonable time.
I have come up with a greedy algorithm that can do well in some cases, here it is:
Cheese Tomato Bread
Alice 4 3 3
Bob 2 4 5
Cindy 5 1 3
1- for each Person, find the Food among remaining foods that is preferred, assign that food to the person. 2- eliminate the chosen food from the list of available foods 3- repeat until you are left with the last person
in my going step by step it would look like this:
Step 1:
Cheese Tomato Bread
Alice *4 - -
Bob - 4 5
Cindy - 1 3
Step 2:
Cheese Tomato Bread
Alice *4 - -
Bob - - *5
Cindy - 1 -
Step 3:
Cheese Tomato Bread
Alice *4 - -
Bob - - *5
Cindy - *1 -
This will take n steps as opposed to n!, and in this case gives us a reasonable answer (10) but in other situations the discrepancy between optimal solution and greedy solution is huge:
preferance vector: (Preference score for Cheese, Tomato and Bread in order)
Alice (3,2,1)
Bob (9,1,2)
Cindy (5,0,9)
brute force: try all combos
total score for [Alice,Bob,Cindy]: 13
total score for [Alice,Cindy,Bob]: 5 //greedy!!!
total score for [Bob,Cindy,Alice]: 10
total score for [Bob,Alice,Cindy]: 20 //best
total score for [Cindy,Bob,Alice]: 7
total score for [Cindy,Alice,Bob]: 9
