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
  • $\begingroup$ What did you want ? $\endgroup$
    – Saikat
    Jun 26, 2016 at 14:31
  • $\begingroup$ The person who answered the question originally left a comment pointing to "The assignment problem" page on Wikipedia. After leaving an answer he/she subsequently deleted the comment, thereby making me look like an idiot $\endgroup$ Jun 26, 2016 at 20:56
  • $\begingroup$ It happens xD. ${}$ $\endgroup$
    – Saikat
    Jun 27, 2016 at 6:53

1 Answer 1


This is an instance of the assignment problem. There are polynomial-time algorithms for solving the assignment problem, e.g., using the Hungarian algorithm (or other algorithms).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.