Prev: HTML5, geolocation and privacy implications
Next: ANN: Seed7 Release 2010-06-06
From: Ben Bacarisse on 5 Jun 2010 11:59
Frederick Williams <frederick.williams2(a)tesco.net> writes:

> 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.
<snip>
>> 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?

Not particularly, I don't think, but for a once off problem I don't
think that investigating complex methods is worth it.

> 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 am not sure this maps exactly onto the problem you quoted (though that
does not matter -- it's interesting in its own right). In your case you
either want to control your monthly spending tightly (so you can't buy a
60 pound book unless you underspent in a previous month) or you aim to
buy the books as quickly as possible; i.e. that minimising n is an
important factor in the quality of the result.

Even so, it is worth trying a simple greedy algorithm:

Try to form n = sum(M)/T sets (12 in your case).
Sort M.
While M not empty:
add head(M) to set k which has the least sum(M_k).

If you care about capping the spend, you will need to sort the sets so
that underspending precedes overspending. If the target n had been
fractional, you'd have to decide between the merits of over-spending for
floor(n) months or underspending for ceil(n).

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

It is certainly interesting since it is slightly different to the usual
(partition M into 2 sets that sum to the same value; often generalised
to n sets).

--
Ben.
From: Frederick Williams on 5 Jun 2010 12:04
Ben Bacarisse wrote:

> Even so, it is worth trying a simple greedy algorithm:
>
> Try to form n = sum(M)/T sets (12 in your case).
> Sort M.
> While M not empty:
> add head(M) to set k which has the least sum(M_k).

Thanks, I'll try that, it's only for fun in any case.

--
I can't go on, I'll go on.
From: Patricia Shanahan on 5 Jun 2010 13:34
Frederick Williams wrote:
....
> 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.

You could reduce your problem to a different model, resource constrained
project network analysis. You have a project that will be completed when
you have read all the books on your list. There are two types of tasks
in the project, buying a book and reading a book.

There are, I assume, some dependencies in the reading order, because you
need understanding you will gain from one book in order to read a more
advanced book on similar topics. Each "Read book X" task is also
dependent on completion of a "Buy book X" task that consumes some amount
of money.

The objective is to schedule the tasks in a way that respects the
dependencies and consumes no more than 50*t pounds for the book buying
tasks in the first t months, for all t from 1 to completion.

Patricia
From: Frederick Williams on 5 Jun 2010 14:52
Patricia Shanahan wrote:
>
> Frederick Williams wrote:
> ...
> > 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.
>
> You could reduce your problem to a different model, resource constrained
> project network analysis. You have a project that will be completed when
> you have read all the books on your list. There are two types of tasks
> in the project, buying a book and reading a book.
>
> There are, I assume, some dependencies in the reading order,

That is a good point that I had overlooked! One work is in two volumes
(to be read in order) and another is in four (ditto); each volume is a
separate book on my list. Also on the list are the six books of
Trollope's(*) Barchester novels; though it isn't necessary to read them
in order, I would prefer to. Perhaps the problem is altogether
different from that which I posed.

(*) John Major was a fan and he famously remarked that he liked to curl
up in bed with a trollope (which happily may be spelled with an 'e').

> because you
> need understanding you will gain from one book in order to read a more
> advanced book on similar topics. Each "Read book X" task is also
> dependent on completion of a "Buy book X" task that consumes some amount
> of money.
>
> The objective is to schedule the tasks in a way that respects the
> dependencies and consumes no more than 50*t pounds for the book buying
> tasks in the first t months, for all t from 1 to completion.
>
> Patricia


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