给定一份食谱列表和自有食材列表，哪种算法最适合确定 "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 种成分
您可以transform/manipulate您认为合适的数据
评分标准是你能多高效地制定一个算法来回答“考虑到我已经拥有的成分，我应该添加哪种成分来制作最多的食谱”
一个人可以随机 add/remove 成分，并且必须能够回答“哪种成分？”高效提问
Space 复杂度暂时可以忽略
然后的目的是设计一个数据结构+算法，无论计算多么复杂，都可以实现快速查询。 'grading' 是这些未来查询的速度

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

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

Answer 3

根据食谱创建一个 trie。对于每个查询，递归查询的子序列和一个允许的通配符，遍历 trie。（食谱和查询都应该以相同的方式对成分进行排序。）

给定一份食谱列表和自有食材列表，哪种算法最适合确定 "Which ingredient could I add to access the most recipes?"

Given a list of recipes a list of owned ingredients, which algorithm is best to determine "Which ingredient could I add to access the most recipes?"

algorithm

performance

graph-theory

coding-efficiency