Algorithms – Solving the Optimal Recipe Problem

algorithmsdynamic programming

Suppose I have a list of Ingredients In My Fridge which are going off soon, and a list of Recipes which use up various Ingredients. (Some of which I don't currently have.)

Is there an algorithm which produces the optimal set of Recipes, where an optimal set maximises the number of Ingredients In My Fridge used up and minimises the number of Ingredients I Have To Buy From The Store?

(Alternate formulation: In a card game, I can combine some Cards according to various Rules; I can also obtain new Cards in various ways. How do I find the best set of Rules to use up the most Cards I have for the minimum effort in obtaining new Cards?)

Best Answer

This is the Exact Cover problem, one of the original 21 problems shown by Karp to be NP-complete in his classic 1972 paper that established the importance of NP-completeness.

Wikipedia's description is:

given a collection S of subsets of a set X, an exact cover is a subcollection S* of S such that each element in X is contained in exactly one subset in S*.

The basic problem is, given S and X, does S contain an exact cover of X?

Here X is the set of contents of your refrigerator, and S is the collection of recipes. The task is to find a subset S* of recipes such that each ingredient from X is used by exactly one recipe.

Exact Cover is known to remain NP-complete even when every recipe requires no more than 3 ingredients. If every recipe has 2 or fewer ingredients, there is a polynomial-time algorithm based on finding a maximal matching in a bipartite graph.

The analogous problem, of whether there is a cover S* that covers at least n elements of X, is also NP-complete. Similarly, one can rephrase this as an optimization problem: find the subset S* that covers the maximum possible number of elements. An efficient solution to this optimization problem would solve the NP-complete decision problem, so is at least as difficult as the decision problem.

As is usual with NP-complete problems, one can say the following:

  1. A good algorithm that works for all instances of the problem is certainly out of reach at present, and probably does not exist.

  2. Branch-and-bound tree search will find a good solution quickly for many instances of the problem, and for small instances.

  3. Straightforward approaches (say, always selecting the recipe with the greatest number of available ingredients) may produce results that are never too far from optimal. There is a lot of research on this sort of thing, and it should not be hard to uncover some.

Wikipedia also mentions an algorithm of Donald Knuth which efficiently performs an exhaustive search of the solution space (which may be very large) by representing the recipes as rows of a matrix.

Related Topic