The optimal recipe problem

Question

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?)

Answer 1

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.

Answer 2

sounds like a path finding problem, you start at a node X and want to move several steps with the least cost.

cost is increased when you buy things and stays the same when you don't.

I suggest a flood-fill or minimax with alfa-beta culling until you find a node where your fridge is empty. (after which you will need to buy anyway)

Answer 3

The approach that I would take is a least-errors approach.

1) Create a set of symbols to represent each food stuff.

2) Represent the contents of your fridge as a string of symbols. The string is ordered and multiple items are represented as multiple symbols. Liquids, etc, should be represented by multiple cup-fractions (i.e., 6 x 1/4 cup of milk).

3) Represent each recipe the same way.

Now, do a least errors pattern match of each recipe string against the fridge string.

I had experience, once upon a time, with Early recognizers. I don't know if that helps.

Answer 4

What about using an hermeneutic approach give every recipy certain points based on different criteria. E.g buying an ingredient 5 points for every ingredient. The one with lowest points wins