给定一个食谱列表，一个拥有的成分列表，哪种算法最好确定"Which ingredient could I add to access the most recipes?"

Question

我希望这个长长的标题能很好地解释这个问题。这感觉像是一个名义问题，所以我怀疑有一个已知的算法来解决这个问题，或者它可能映射到NP。

给定一本食谱，格式为

cookbook = {
recipe1: [ingredient1, ingredient2, ingredient35],
recipe2: [ingredient1, ingredient8, ingredient12], 
recipe3: [ingredient10, ingredient22, ingredient35],
...
}

和成分列表形式

ingredients = {
ingredient1: true, //owned
ingredient2: false, //unowned
ingredient3: true,
...
}

哪种算法能有效地回答"你可以添加哪种成分来完成最多的食谱?">

假设

• 有大量的食谱&成分
• 一个配方的配料不得超过10种
• 你可以转换/操作数据，但你认为合适
• 评分标准是你的算法的效率如何，它可以回答"我应该添加哪种成分来制作最多的食谱，因为我已经拥有了这种成分";
• 一个人可以随意添加/删除配料，并且必须能够回答"哪种配料?"问题有效的
• 空间复杂度现在可以忽略
• 然后的意图是设计一个数据结构+算法，无论计算可能是复杂的，它允许快速查询。"分级"是那些未来的查询有多快

Answer 1

伪代码

bestIngredient = 0
bestCount = 0
Loop I  over owned ingredients
count = 0
Loop R over recipes
If I completes R
increment count
if count > bestCount
bestCount = count
bestIngredient = I

添加成分I时:

Loop R over recipies
If R needs I 
Add I to R

Answer 2

根据食谱创建一个tree。对于每个查询,递归查询的子序列和一个允许通配符,行走单词查找树。(食谱和查询都应该以相同的方式对食材进行排序。)

Answer 3

score = empty hashmap
for each R in recipes
missing = empty list
for each I in R
if ingredients[i] = false
missing += I
if size(missing) = 1
I = missing[0]
score[I]++
result = choose key I in score with maximum value