Best strategy to distribute number into groups eve

Question

You have two list of integer number A={1,3,60,24} and B={14,54,3}, the order and list length is undetermined. What is the best strategy to put numbers in A into B so that the variance of result in B is as balanced as possible. You do not have to put all numbers in A into B if there is no space available. But you have to put number if there is space available

I am thinking of applying Branch and Bound, and however, I am not sure how to find a prune condition such as calculating variance of the sub-problem(not completely filled) to tell which branch to cut?

Any ideas?

Answer 1

Create list c from Difference between A and B that C[i]=A[i]-B[i].then you should find All elements that sum of them is close to zero.it is like as this problem. but in this question you have a negative number.and you must find a subset that sum of them is close to zero. I think this is a NP-Complete problem.

Answer 2

The problem you are describing is the partition problem(http://en.wikipedia.org/wiki/Partition_problem). Finding an optimal solution is NP-complete however there are a number of approximations that are almost perfect for most cases.

In fact, the algorithm you described is the way playground kids would pick teams. This greedy algorithm performs remarkably well if the numbers in the set are of similar orders of magnitude. Sure, it's not the best solution, but considering how the problem is NP-complete, it's pretty gosh darned good for it's simplicity.

This article in American Scientist gives an excellent analysis of the problem and you should go through and read it: The Easiest Hard Problem(http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-problem).