Algorithm for seating groups of people?

I'm intereste开发者_StackOverflow社区d in writing an application that can determine how to seat groups of 2-10 people at tables that can hold 10 people. There will probably be about 15 tables and 140 people total. I don't want to break up any of the groups of people.

It seems like it might be a common problem and I was wondering if anyone had any suggestions on where I should start to look for a solution to this. Any links or suggestions appreciated.

This is the bin packing problem.

This is just a variation on the standard "Knapsack problem"

When we had this problem in school we solved it with as a TSP problem.

This is the bin packing problem, which is NP-Hard (it's not easy to find the best answer, and it's not easy to check if an answer is the best).

The groups of people are an individual objects, with the volume = the number of people people in the group. The tables are the bins of size 10.

There are a few approximation algorithms out there, which should be easy to find knowing that you should google for bin packing.

However, your problem is relaxed (in some ways) because you have 10 tables -- i.e., you are not trying to fit the people on the minimum number of tables. If 10 tables is the OPTIMAL solution, you will have trouble finding the solution (if it even exists), but if the optimal is really 7 or 8, finding the solution will be easy. It all depends on the group distributions.