the dining mongers problem
greg at mccarroll.org.uk
Thu Oct 12 21:57:49 BST 2006
So, I'm having some friends around tomorrow night so I asked them
like to eat, their 'leader' suggested Pizza so this reminded of a
that might be interesting from a computational or algorithmic point
of view - I
really don't know as I haven't attempted it yet, anyway here it is.
You have N mongers coming around.
They all want to be able to have H (hunger) pieces each
Each pizza has S slices
You want to order the minimum number of pizza's, so i guess thats
You ask them all for 3 toppings they want and ask them for 3 toppings
they cannot eat pizza with, e.g. they are fussy like me (sweetcorn)
or they maybe are allergic to seafood. (I guess you could generalise
both these numbers).
There is a set menu of toppings (although i'm guessing this could
be ignored for the union of all the topics they want).
How can you please the mongers the most?
There is a basic solution that makes everyone not unhappy, of ordering
ceil((N*H)/s) pizza's with no toppings on any of them, i.e. bread ;-)
Anyway I don't know if this will turn out to be an interesting
not, but I thought I might as well share it.
p.s. full solutions that support data entry for N people will be
p.p.s. i'm guessing some of the interest might come out of how some
spoil it for others.
p.p.p.s. and of course this can be brute forced.
More information about the london.pm