We are running a restaurant. Unfortunately due to mysterious reasons, we cannot tell our chef what recipes to make, we can only prepare him the ingredients for the meals. Fortunately our chef has memorized all possible recipes, therefore if we carefully designate separate tables on which we put recipe ingredients (e.g. ingredients for meal_1 will always go on table_2) he can always make correct meals (he assumes all ingredients for a meal are on one table). Of course tables are expensive so we want to use as few as possible (the solution does not have to be optimal, but hopefully close to it).

Examples (letters are ingredients and numbers):

These three recipes are compatible (it is guaranteed that the chef can only make the meals we want him to make) and the ingredients can be on the same table.

  • a b -> meal_1
  • c d -> meal_2
  • a c e -> meal_3

These two recipes are incompatible and cannot be on the same table, because our chef could just cook meal_5 and have c ingredient left.

  • a b c -> meal_4
  • a b -> meal_5

Here first two recipes are compatible, but the third one is incompatible and cannot be on this table (n smaller recipes can make a bigger one)

  • a b -> meal_6
  • c d -> meal_7
  • a b c d -> meal_8

Algorithm inputs: recipes (list of ingredients) Expected output: recipes sorted into sets of compatible recipes (as few sets as possible)

  • $\begingroup$ What is your question? $\endgroup$
    – Nathaniel
    Nov 5 at 19:32
  • $\begingroup$ My question is how would an algorithm to solve this problem look like. Sorry if that wasn't clear enough. I think once we have the incompatible recipes figured out, we can use graph coloring algorithms to figure out the number of tables. $\endgroup$ Nov 6 at 7:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.