algorithm - 给定食谱列表和拥有的成分列表，哪种算法最适合确定 "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 种
• 您可以按照您认为合适的方式转换/操作数据
• 评分标准是您能否高效地制定一个算法来回答“考虑到我已经拥有的成分，我应该添加哪种成分来制作最多的食谱”
• 一个人可以随机添加/删除成分，并且必须能够回答“哪种成分？”高效提问
• 暂时可以忽略空间复杂度
• 然后的目的是设计一个数据结构+算法，无论计算多么复杂，它都可以实现快速查询。 “评分”是指 future 查询的速度

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