the dining mongers problem

[McGlinchy, Alistair]

> 	How can you please the mongers the most?

I'm not sure that is a well defined question (ether from a facetious
point of view or at face value) so I have attempted to clarify.

The principal restriction (R)is that \each Monger M_n (n \in N) their
hunger H( M_n )will be sated with slices of pizza containing toppings
that are not in their deny list.

There are two competing optimisations here:
- minimising for the number of pizzas needed to reduce costs
- maximimsing the number of hits where Monger M_n is sated with a slice
containing one or more toppings from their "prefer" list.
 
If you assume that you are only considering solutions where the number
of pizzas purchased is the least number possible to meet R.   [ ie
wasted pizza/money is worse than super-contented Mongers.]

The problem breaks down to:
A> Computing the minimum number of pizzas needed to satisfy the R.
(Start at 1 pizza and work up until you get any result meeting
restriction R)

B> Computing all possible pizza permutations for the given min number of
pizzas and for each combination taking the maximum number of "prefer
hits".

<hand waving begins> 
I claim that restriction R is just a rewording of the Rook Polynomial
problem.  http://www.cs.uleth.ca/~holzmann/notes/rook.pdf  and hence the
problem is solved.
</>

Cheers,

Alistair


PS Apologies for remaining on-topic.

**********************************************************************
Registered Office:
Marks and Spencer plc
Waterside House
35 North Wharf Road
London
W2 1NW

Registered No. 214436 in England and Wales.

Telephone (020) 7935 4422
Facsimile (020) 7487 2670

<<www.marksandspencer.com>>

Please note that electronic mail may be monitored.

This e-mail is confidential. If you received it by mistake, please let us know and then delete it from your system; you should not copy, disclose, or distribute its contents to anyone nor act in reliance on this e-mail, as this is prohibited and may be unlawful.
2005