
Re: Seeking an algorithm
Posted:
Sep 29, 2011 4:27 PM


On Thu, 29 Sep 2011 21:13:16 +0100, Helmut Richter <hhrm@web.de> wrote:
> On Thu, 29 Sep 2011, Peter Percival wrote: > >> Given a finite set of numbers, find a partition of it into two sets A >> and B so >> that the sum of A's elements is as close to the sum of B's elements as >> possible. Clearly, one could try all partitions, but if the initial >> set is >> large, that might take a long time. >> "Numbers" might mean real numbers, positive real numbers, integers, or >> positive integers. Perhaps there are different answers in these four >> different cases. > > Not much difference. > >> My first thought for positive numbers of either kind is: >> (i) Order the numbers according to decreasing size; >> (ii) put the first in A; >> (iii) put the second, third, etc, in B until either all numbers are >> used, or >> the B sum just exceeds the A sum; >> (iv) put the next, next after it, etc in A until either all numbers are >> used, >> or the A sum just exceeds the B sum; >> (v) continue thus, stopping when all numbers are used. >> Is this a good method? "Good" meaning the (or a) most equal partition >> is >> always found, and quickly so. I suspect it will sometimes fail to find >> the >> most equal partition. > > If the numbers are {2, 2, 2, 3, 3}, your algorithm puts the two 3 one > into > A and the other into B. There is a different solution which is better.
Thank you. But I would call {2, 2, 2, 3, 3} a multiset, rather than a set.
> You can use your algorithm for a bound on the best solution. That is, for > this example, when your algorithm has a sum of 7 in A and of 5 on B, then > every other algorithm can be stopped as soon as one set gets a sum of 7 > or > more. This can save a lot of time when trying when the initial guess is > already good. > > You can also start with your algorithm and then find pairs of numbers > having exactly or approximately the right difference, so that a solution > is improved by swapping them. For a practical approximation solution, > this > might often suffice. But it will not necessarily find an optimal > solution, > to wit when not single numbers have to be swapped but subsets of them  > thus ending up with more or less the original problem. > > The real optimal solution is much more complicated. See for instance > http://en.wikipedia.org/wiki/Subset_sum_problem .
Thank you for the reference. I had supposed the problem(*) was known, but did not know its name, so I could not look anything up.
(* I will just remark on how it came to my mind. I was looking at two piles of books on a table, and I wondered if there was some systematic way of making two piles so that they were of equal, or nearequal, height, so that a large book (an atlas, say) could be rested on the top of each pile and be horizontal, or nearly so. So mine was the positive reals problem.)
 Using Opera's revolutionary email client: http://www.opera.com/mail/

