Best strategy to distribute number into groups evenly

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?

Is the problem on-line (i.e., can I see the entire set A before I start deciding whether a particular element should be added to B)? — chepner, Mar 06 '13 at 22:02
Yes, We consider case when A and B can all be put into memory first — f g, Mar 06 '13 at 22:18

score 1 · Answer 1 · answered Mar 07 '13 at 14:04

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).

In principle, that is correct. Technically, i am wondering how to prune wisely and keep track of visit — f g, Mar 08 '13 at 16:36

score 0 · Answer 2 · edited May 23 '17 at 11:51

0

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.

edited May 23 '17 at 11:51

Community

1
1

answered Mar 07 '13 at 07:27

amin k

1,692
1
12
28

it is a NP-complete problem. You made a same mistake as I do. What u are doing is minimizing the remaining in B instead of minimizing variance of distributed number in B. – f g Mar 08 '13 at 16:35

Best strategy to distribute number into groups evenly

2 Answers2

Linked