# Knapsack problem with multiple constraints

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

-
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? –  Paresh Nov 23 '12 at 6:30
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. –  Paresh Nov 23 '12 at 12:06
hey guys, someone misunderstood my question and edited the original. im fixing it now –  bouncingHippo Nov 24 '12 at 2:44
If it's Knapsack it's unlikely to be solvable in polynomial time (by an easy algorithm). –  Raphael Nov 24 '12 at 15:26
@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)? –  Paresh Nov 26 '12 at 15:07

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.