the dining mongers problem

Greg McCarroll greg at
Thu Oct 12 21:57:49 BST 2006

So, I'm having some friends around tomorrow night so I asked them  
what they'd
like to eat, their 'leader' suggested Pizza so this reminded of a  
social problem
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
	whatever ceil((N*H)/S)

	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  
problem or
not, but I thought I might as well share it.


p.s. full solutions that support data entry for N people will be  
tested ;-)
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 mailing list