Prev: HTML5, geolocation and privacy implications
Next: ANN: Seed7 Release 2010-06-06
From: Frederick Williams on 5 Jun 2010 06:16
Consider this problem:

A multiset M of positive integers is given.
A "target" positive integer T is given.
Problem: partition M into submultisets M_0, M_1, ..., M_n
so that the sum of the numbers in each M_i is
as close as possible to T.

Is there an algorithm for solving this? Yes, clearly there is. But is
there an algorithm that a not especially competent C programmer (= me:-)
could turn into code that could handle an M with about 40 elements in a
reasonable length of time?

--
I can't go on, I'll go on.
From: Pascal J. Bourguignon on 5 Jun 2010 06:56
Frederick Williams <frederick.williams2(a)tesco.net> writes:

> Consider this problem:
>
> A multiset M of positive integers is given.
> A "target" positive integer T is given.
> Problem: partition M into submultisets M_0, M_1, ..., M_n
> so that the sum of the numbers in each M_i is
> as close as possible to T.
>
> Is there an algorithm for solving this? Yes, clearly there is. But is
> there an algorithm that a not especially competent C programmer (= me:-)
> could turn into code that could handle an M with about 40 elements in a
> reasonable length of time?

Well, the problem here is that you don't define "close".


For example, M={7,8,10}, T=10,

S1={{7,8},{10}} is "close", since there's a submultiset whose sum is
T, and just one other whose sum is 5 away.

On the other hand, S2={{7},{8},{10}} is "closer" because all the
submultiset sums are less than 3 away to T, or "less close" since
there are more submultisets whose sums are not T.



--
__Pascal Bourguignon__ http://www.informatimago.com/
From: Ben Bacarisse on 5 Jun 2010 07:46
Frederick Williams <frederick.williams2(a)tesco.net> writes:

> Consider this problem:
>
> A multiset M of positive integers is given.
> A "target" positive integer T is given.
> Problem: partition M into submultisets M_0, M_1, ..., M_n
> so that the sum of the numbers in each M_i is
> as close as possible to T.

This is close to the multiset partition problem, specifically when T =
sum(M)/2 unless your notion of "as close to" is odd enough to prefer
some partition into more than 2 sets. The multiset partition problem is
NP-complete and it looks as if yours is too.

To pin it down you'd need to specify "as close to". The obvious choice
being the partition which minimises max(abs(sum(M_k) - T)) for k=1..n.
Some applications might need a better measure -- minimising the sum of
the squares of the differences for example.

> Is there an algorithm for solving this? Yes, clearly there is. But is
> there an algorithm that a not especially competent C programmer (= me:-)
> could turn into code that could handle an M with about 40 elements in a
> reasonable length of time?

The multiset partition problem (MPP) has easy instances and hard
instances and so does your problem. When T is large the optimum will
have n=0 and M_0=M. The hardest cases will probably be when T<=sum(M)/2
and when the range of numbers in M is large (because that is when the
MPP gets hard).

When the range is small, the simple greedy algorithm (guess n from T and
sum(M), sort M and put successively smaller numbers in to the set whose
sum is currently furthest from T/n) will probably do quite well. If
your instances tend to be hard ones, then you will probably have to
look at statistical methods like simulated annealing.

Do you know anything about the range of the numbers in M and values of T
that you will have to solve for?

--
Ben.
From: Frederick Williams on 5 Jun 2010 11:10
"Pascal J. Bourguignon" wrote:
>
> Frederick Williams <frederick.williams2(a)tesco.net> writes:
>
> > Consider this problem:
> >
> > A multiset M of positive integers is given.
> > A "target" positive integer T is given.
> > Problem: partition M into submultisets M_0, M_1, ..., M_n
> > so that the sum of the numbers in each M_i is
> > as close as possible to T.
> >
> > Is there an algorithm for solving this? Yes, clearly there is. But is
> > there an algorithm that a not especially competent C programmer (= me:-)
> > could turn into code that could handle an M with about 40 elements in a
> > reasonable length of time?
>
> Well, the problem here is that you don't define "close".

Agreed. Defining "close" may be considered to be part of the problem!

> For example, M={7,8,10}, T=10,
>
> S1={{7,8},{10}} is "close", since there's a submultiset whose sum is
> T, and just one other whose sum is 5 away.
>
> On the other hand, S2={{7},{8},{10}} is "closer" because all the
> submultiset sums are less than 3 away to T, or "less close" since
> there are more submultisets whose sums are not T.

Let's say add the differences and close means minimize that sum. So in
this case since both sums-of-differences are 5 we can say that both
solutions are to to be offered as equally good.

--
I can't go on, I'll go on.
From: Frederick Williams on 5 Jun 2010 11:30
Ben Bacarisse wrote:
>
> Frederick Williams <frederick.williams2(a)tesco.net> writes:
>
> > Consider this problem:
> >
> > A multiset M of positive integers is given.
> > A "target" positive integer T is given.
> > Problem: partition M into submultisets M_0, M_1, ..., M_n
> > so that the sum of the numbers in each M_i is
> > as close as possible to T.
>
> This is close to the multiset partition problem, specifically when T =
> sum(M)/2 unless your notion of "as close to" is odd enough to prefer
> some partition into more than 2 sets.

> The multiset partition problem is
> NP-complete and it looks as if yours is too.
>
> To pin it down you'd need to specify "as close to". The obvious choice
> being the partition which minimises max(abs(sum(M_k) - T)) for k=1..n.
> Some applications might need a better measure -- minimising the sum of
> the squares of the differences for example.
>
> > Is there an algorithm for solving this? Yes, clearly there is. But is
> > there an algorithm that a not especially competent C programmer (= me:-)
> > could turn into code that could handle an M with about 40 elements in a
> > reasonable length of time?
>
> The multiset partition problem (MPP) has easy instances and hard
> instances and so does your problem. When T is large the optimum will
> have n=0 and M_0=M. The hardest cases will probably be when T<=sum(M)/2
> and when the range of numbers in M is large (because that is when the
> MPP gets hard).
>
> When the range is small, the simple greedy algorithm (guess n from T and
> sum(M), sort M and put successively smaller numbers in to the set whose
> sum is currently furthest from T/n) will probably do quite well. If
> your instances tend to be hard ones, then you will probably have to
> look at statistical methods like simulated annealing.
>
> Do you know anything about the range of the numbers in M and values of T
> that you will have to solve for?

M has about 40 elements ranging from 1000 to 6000 or so, sum M is about
60000 and T is about 5000. So T < sum(M)/2, is that bad?

It's a real-world problem but not an important one: I wish to buy about
40 books , the prices being the elements of M, total cost about 600.00
pounds. I can afford to spend about T = 50.00 pounds per month. How
should I plan my spending?

I can of course just eye-ball the list, or (and this is probably what I
will do) just buy the books I want most, first; but I wondered if the
problem generalized was a known and/or interesting one.

Confession: I'd never even heard of the multiset partition problem!

> Ben.


--
I can't go on, I'll go on.
 |  Next  |  Last
Pages: 1 2
Prev: HTML5, geolocation and privacy implications
Next: ANN: Seed7 Release 2010-06-06