我希望長標題能很好地解釋這個問題。這感覺像是一個名義上的問題，所以我懷疑有一個已知的演算法，或者它可能映射到 NP。
給定一本食譜形式的
cookbook = {
recipe1: [ingredient1, ingredient2, ingredient35],
recipe2: [ingredient1, ingredient8, ingredient12],
recipe3: [ingredient10, ingredient22, ingredient35],
...
}
以及表格中的成分串列
ingredients = {
ingredient1: true, //owned
ingredient2: false, //unowned
ingredient3: true,
...
}
哪種演算法可以有效地回答“您可以添加哪種成分來完成最多的食譜？”
認為
- 有大量的食譜和配料
- 給定的配方不會超過 10 種成分
- 您可以按照自己認為合適的方式轉換/操作資料
- 評分標準是您制作一個演算法的效率如何，該演算法可以回答“考慮到我已經擁有的成分，我應該添加哪種成分來制作最多的食譜”
- 一個人可以隨意添加/洗掉成分，并且必須能夠回答“哪種成分？” 有效地提問
- 空間復雜度暫時可以忽略
- 然后意圖是設計一個資料結構 演算法，無論計算復雜度如何，它都允許快速查詢。“分級”是未來查詢的速度
uj5u.com熱心網友回復：
偽代碼
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
uj5u.com熱心網友回復：
從食譜中創建一個嘗試。對于每個查詢，遞回查詢的子序列和一個允許的通配符，遍歷樹。（食譜和查詢都應該以相同的方式對成分進行排序。）
uj5u.com熱心網友回復：
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313577.html
上一篇：計算給定陣列的最小成本