0
$\begingroup$

I am unsure if I have even identified the problem correctly, but reading up on knapsack problem seems the closest to what I am trying to solve:

A cook has $k$ ingredients of $p$ quantities. Given a list of $n$ unique recipes, each consisting varying ingredients of varying quantities. Now, the cook would like to use all ingredients on ONE recipe with minimal leftovers.

What is his solution? And can it be determined in $O(\log n)$ time?

Sample input

500 pounds of flour 300 mg sugar 5 mg of vanilla pods 20 eggs

Database of possible recipes:

Thai Fried Noodles (doesn't contain vanilla or flour, but contains 1 tablespoon of sugar)

Tiramisu (doesn't contain flour and vanilla but contains 3 tablespoons of sugar and 8 eggs)

Anna's Special Tiramiu (doesn't contain flour and vanilla but contains 1 tablespoons of sugar and 8 eggs)

Truffle Tagliatelle (doesn't contain any input ingredients)

EDIT Cost/benefit decision:

Given the sample input, Tiramisu recipe is the most preferred because among the 4 recipes in the database, it contains the most number of input ingredient type (2 of 4 types), and the most number of input ingredient quantity.

Expected result where 1) is the top search result of relevance: 1) Tiramisu 2) Anna's Special Tiramisu 3) Thai Fried Noodles 4) Truffle Tagliatelle

EDIT: I believe my question is a variant of the integer knapsack problem

Improve this question
$\endgroup$
18
  • 3
    $\begingroup$ First of all, I don't think the question is well defined. What do you mean by "to minimize waste"? Does not being able to use 1 egg out of 8 as bad as not being able to use 1ml of milk? More formally, there is no well-defined cost/penalty function of not using various ingredients. Secondly, what is $n$? Is it the number of ingredients or the number of recipies? $\endgroup$ Commented Nov 23, 2012 at 6:30
  • 2
    $\begingroup$ After the edit, I assume the quantities of varying ingredients are comparable. I also assume, that there are $m$ ingredients available to the cook. Under these assumptions, just checking if a given recipe can be made using the ingredients will take $O(m)$ time. To find all recipes which are feasible will take $O(mn)$ time. If you assume all recipes are feasible, you still need to check each and every one in $O(mn)$ time, unless they are structured in some special order. $\endgroup$ Commented Nov 23, 2012 at 12:06
  • $\begingroup$ hey guys, someone misunderstood my question and edited the original. im fixing it now $\endgroup$ Commented Nov 24, 2012 at 2:44
  • $\begingroup$ If it's Knapsack it's unlikely to be solvable in polynomial time (by an easy algorithm). $\endgroup$ Commented Nov 24, 2012 at 15:26
  • 1
    $\begingroup$ @bouncingHippo To formulate an algorithm, the problem needs to be defined precisely. So for your sample input, how does 500 pounds of flour compare with 300 mg sugar or to 20 eggs. Suppose one recipe A requires everything except 200 pounds of flour, while another recipe B requires everything except 300 mg sugar. Which recipe should be preferred? Should A be preferable just because the number 200 is greater than 300? Or should they be in the same units (in which case, what about 20 eggs)? $\endgroup$ Commented Nov 26, 2012 at 15:07

1 Answer 1

Reset to default
1
$\begingroup$

I assume you can compare two recipes and say which would be preferable to the other. That is, you can define an order between them. Then:

  1. You need to find appropriate recipe only once (or very few times). A simple scan through all the recipes is the only way possible. You need to look at every recipe at least once to be able to see if it is good enough or not. This will give linear complexity.
  2. You have to find appropriate recipes repeatedly for a lot of different baskets. Then, it would make sense to order the recipes in a way that searching would be faster. You might want to sort the recipes first once, in $O(n\log n)$ time. Then, whenever you encounter a basket of ingredients for which you want to find the best recipe, you search the sorted list of ingredients using binary search in $O(\log n)$ time. Thus, the pre-processing phase (sorting) will be slow, but subsequent queries will be fast. This will be beneficial only when you have millions of recipes and want to search the best matched recipe for different baskets hundreds or thousands of times each second.

Admittedly, this is a little vague, but based on the given information, this is the best I can give.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.