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
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:


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.
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.