Algorithm to find the optimal strategy to feed your cousin (Long question)

Question

I have a programming problem, instead of describing the whole domain it's easier for me to create an analogy. The numbers I use in this example are completely arbitrary.

Your cousin is coming over later and you must feed him dinner. He will only eat what he randomly decides he wants when he gets to your house and will not tell you ahead of time what that will be. However, you have been given a list of recipes that you know for certain he will choose from.

All of the recipes are soups that are made from one or more ingredients and the recipes call for small, medium, or large cans of each ingredient. There are no rules for how many cans are required or what sizes they can come in, but you don't care about waste so it's fine if you use a can that is larger than the recipe calls for.

Your cousin isn't very strict about sticking to the recipe, in fact, only half of the ingredients have to even be in the pot for him to call the recipe complete!

Unfortunately you have exactly zero of the ingredients needed and you only have time to make a short shopping trip before he arrives. Additionally, the store you're shopping at will only allow you to leave if you have exactly 5 small cans, 4 medium cans and 3 large cans. Once again, you don't care about waste so getting extra, unused cans is perfectly okay.

Since you don't know what recipe you'll be demanded to make, you want to try to be prepared to cook as many recipes as possible, but because of the restrictions on number of cans you can buy you will not be able to buy all of them.

I am attempting, essentially, to find an algorithm that takes the list of recipes and then suggests a shopping list that covers the maximum number of recipes.

Summary of rules

• Demanded recipe is random
• You only need to adhere to 50% of the ingredients called for
• You must buy exactly 5 large cans 10 medium cans and 20 small cans
• Waste is fine, using cans larger than needed or buying extra cans is okay
• Using larger cans does not constitute completing the recipe more than smaller cans
• For example: A 3-ingredient recipe is still only 33% complete from one can regardless of size.
• You will be asked to prepare exactly one recipe, no more
• Currently there are 25 recipes on the list, but more get added each time your cousin visits!
• There are no recipes with more than 15 ingredients, some have zero ingredients but we just ignore them
• Practically there's probably around 75 ingredients among the recipes

My attempts

My first idea was to iterate through the ingredients and rank them on how much they contribute to each recipe. For example, if a recipe calls for 10 ingredients then our ingredient would have 0.1 added to it's score. If another 2-ingredient recipe used that ingredient it would have a score of 0.1 + 0.5 = 0.6

Each ingredient would have a rank for each can size (Small, Medium, Large)

I would then consider each ingredient by summing the size ranks up to a given size. So for example I would add the Small + Medium + Large ranks together and sort the ingredients on that sum to decide which ingredients I would buy large cans of. Then I would remove those ingredients from the list and do the same thing with Small + Medium ranks.

Then I realized if there were 20 recipes with one ingredient in common, but none of the other ingredients were used anywhere else (even among the 20 recipes) then we would have one ingredient with a huge rank which couldn't even satisfy one recipe.

Then I thought it would be good to include a commonality factor into my calculations: An ingredient would also be ranked on the commonality of it's "friends". An ingredient is "friends" with another if they share the same recipes. If an ingredient has low ranking or uncommon friends then it should rank low too.

I just now realized I might be coming at this backwards, maybe I should compare how much the recipes have in common. If a recipe has a lot in common with many other recipes then covering it will probably cover all of the recipes similar to it.

Any ideas on how to find the solution to this? I cannot believe there hasn't been a graph theory problem similar to mine somewhere out there. I just haven't found it yet.