5

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

  • 5
    This sounds like a variation on the knapsack problem. – user40980 Apr 16 '14 at 15:35
  • I don't think so - I think it's more a cost/benefit analysis. If you can quantify the benefit of using certain rules, and quantify the cost of acquiring new resources, then you can judge the relationship between them to select the best combination. – Daenyth Apr 16 '14 at 15:36
  • Knapsack problem is still a knapsack problem if every item has the same weight. Plus, it is more of a category of problems, not a specific problem. – user22815 Apr 16 '14 at 16:19
  • 1
    Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Apr 16 '14 at 16:19
9

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.

  • 2
    For further discussion that will be completely unhelpful, see my blog post My favorite NP-complete problem. – Mark Dominus Apr 16 '14 at 16:24
  • 1
    If I'm not mistaken, NP-complete is to programmers as Khan is to Kirk. "Khaaaaan!" – Allan Apr 17 '14 at 4:04
0

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)

0

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.

0

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

  • assigning costs to various actions is easy, and basically implied in any optimization problem. The difficult part is finding an optimal solution efficiently. Do you have any suggestion on how “the one with the lowest points” could be calculated? – amon Apr 16 '14 at 17:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.