|
|
Re: Seeking an algorithm
Posted:
Sep 29, 2011 4:27 PM
|
|
On Thu, 29 Sep 2011 21:13:16 +0100, Helmut Richter <hhr-m@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 multi-set, 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 near-equal, 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/
|
|
