1

Suppose there are n numbers let says we have the following 4 numbers 15,20,10,25

There are two container A and B and my job is to distribute numbers to them so that the sum of the number in each container have the least difference.

In the above example, A should have 15+20 and B should have 10+ 25. So difference = 0.

I think of a method. It seems to work but I don't know why.

Sort the number list in descending order first. In each round, take the maximum number out and put to the container have less sum.

Btw, is it can be solved by DP? THX

Bear
  • 5,138
  • 5
  • 50
  • 80
  • 2
    See: [Partition problem](http://en.wikipedia.org/wiki/Partition_problem). Also, [this](http://www.americanscientist.org/issues/issue.aspx?id=3278&y=0&no=&content=true&page=4&css=print) is a great read. – Ani Dec 23 '11 at 03:57
  • See this question: http://stackoverflow.com/questions/5292162/partition-problem – Rafał Dowgird Dec 23 '11 at 06:42
  • 2
    possible duplicate of [divide list in two parts that their sum closest to each other](http://stackoverflow.com/questions/4479479/divide-list-in-two-parts-that-their-sum-closest-to-each-other) – Saeed Amiri Dec 23 '11 at 07:28

1 Answers1

4

  1. In fact, your method doesn't always work. Think about that 2,4,4,5,5.The result by your method will be (5,4,2)(5,4), while the best answer is (5,5)(4,4,2).

  2. Yes, it can be solved by Dynamical Programming.Here are some useful link:

    Tutorial and Code: http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp3.pdf
    A practice: http://people.csail.mit.edu/bdean/6.046/dp/ (then click Balanced Partition)

  3. What's more, please note that if the scale of problem is damn large (like you have 5 million numbers etc.), you won't want to use DP which needs a too huge matrix. If this is the case, you want to use a kind of Monte Carlo Algorithm:

    1. divide n numbers into two groups randomly (or use your method at this step if you like);
    2. choose one number from each group,
      if (to swap these two number decrease the difference of sum) swap them;
    3. repeat step 2 until "no swap occurred for a long time".

    You don't want to expect this method could always work out with the best answer, but it is the only way I know to solve this problem at very large scale within reasonable time and memory.

Timothy
  • 4,467
  • 5
  • 28
  • 51
  • could you elaborate a little as i am really impatient to read it entirely and i see "T[x] will be true if and only if there is a subset of the numbers that has sum x" in the starting of paper. i think the basic idea is of dp is also a knapsack filling problem. – FUD Dec 23 '11 at 13:36