这是我正在解决的问题：
"哈姆雷特中的三个女巫只要有正确的成分。假设在制作健康药剂：蝾螈的眼睛、青蛙的脚趾、蝙蝠（wob）、加法器的叉子（af）和狼的牙齿（tow）。四种反应可以>发生在这些成分之间：
4 eon+2 wob=3 af+4 tow
3丝束+1 tof=2 eon
1 wob+2 af=1 tof
4 tof+7 tow+2 af=1健康药剂假设你能控制反应的顺序，写一个程序可以计算出一个人可以用给定数量的成分。下面是示例输出：如果我有34eon，59 tof，20 wob，5 af，20 tow，我可以做七种健康药剂。"
节选自：奥菲尔·弗里德，吉迪恩·弗里德，大卫·格罗斯曼。"Ruby的计算机科学编程基础"，iBooks。
这是我的解决方案：
ingredients = Hash.new
potion = 0
puts "Welcome to potion brewer! To make a health potion you must combine 4 TOF + 7 TOW + 2 AF. Let's get started.nn"
puts "How many EON do you have?"
ingredients["EON"] = gets.to_i
puts "How many TOF do you have?"
ingredients["TOF"] = gets.to_i
puts "How many WOB do you have?"
ingredients["WOB"] = gets.to_i
puts "How many AF do you have?"
ingredients["AF"] = gets.to_i
puts "How many TOW do you have?"
ingredients["TOW"] = gets.to_i
while (ingredients["EON"] >= 4 and ingredients["WOB"] >= 2)
ingredients["AF"] += 3
ingredients["TOW"] += 4
ingredients["EON"] -= 4
ingredients["WOB"] -= 2
# ==/== DEBUG ==/==
# puts "4 EON and 2 WOB convereted into +3 AF and +4 TOW."
# puts ingredients["EON"]
# puts ingredients["WOB"]
end
while ((ingredients["TOF"]/4) < (ingredients["AF"]/2))
## puts "debug"
if (ingredients["WOB"] >= 1 and ingredients["AF"] >= 2)
ingredients["TOF"] += 1
ingredients["WOB"] -= 1
ingredients["AF"] -= 2
# puts "1 WOB and 2 AF converted to +1 TOF."
else
break
end
end
while (ingredients["TOF"] >= 4 and ingredients["TOW"] >= 7 and ingredients["AF"] >= 2)
potion += 1
ingredients["TOF"] -= 4
ingredients["TOW"] -= 7
ingredients["AF"] -= 2
# ==/== DEBUG ==/==
#puts "Potion created.."
end
puts "nnMade #{potion} potion(s).nn"
for name in ingredients.keys
puts "You have " + ingredients[name].to_s + " " + name + " left.n"
end
无论如何，这是我能想出的解决问题的"最整洁"的方法。我认为我正确地订购了转换，这样在制作药剂时就不会有任何效率低下的问题。。我从书中的例子中得到了想要的结果。
有人能确认它实际上看起来还可以吗/我没有错过一些可以进一步最大化我的药剂的重大优化吗？我找不到太多与第三次转换有关的内容（1ob+2af=1tof）。
谢谢！
有趣的问题！
因此，让我们重新表述一下：目标是计算"健康"药剂，如果这种药剂中的任何成分缺失，则寻找其他可以用来制造缺失成分的药剂。
这听起来是一个递归算法。因此，首先，让我们对"制造药水"问题进行建模。
假设我们有一个药剂配方，一个包含所有所需成分（负值）的散列，以及由此产生的成分，正值。
例如：
4 eon + 2 wob = 3 af + 4 tow
可以写成：
formulae={:eon=>-4,:wob=>-2,:af=>3,:tow=>4}
因此，计算公式将非常简单：
def compute_formulae ingredients,formulae
result=ingredients.clone
formulae.each do |needed,amount|
if ingredients[needed]<-amount
puts "Missing #{needed}" # The is an ingredient missing, we should probably exit now
return nil
else
result[needed]+=amount
end
end
result
end
现在的问题是，当缺少一种成分时该怎么办？根据我们现有的成分，我们必须在配方列表中找到一种可以用来"创造它"的配方
formulas=[
{:tof=>-4,:tow=>-7,:af=>-2,:health=>1},
{:eon=>-4,:wob=>-2,:af=>3,:tow=>4},
{:tow=>-3,:tof=>-1,:eon=>2},
{:wob=>-1,:af =>-2,:tof=>1}
]
formulas.each{|f| f.default=0} # Just ensure that there is de fault value for all ingredients
def find_missing_ingredient ingredients,formulas,missing
formulas.each do | formulae |
if formulae[missing]>0
compute_formulae_ingredient ingredients,formulae
end
end
end
# so basically, the problem is
ingredients={:eon=>34,:tof=>59,:wob=>20,:af=>5,:tow=>20}
ingredients.default=0
while find_missing_ingredient ingredients,formulas,:health
end
现在，有一些小细节，比如主循环（我们需要继续，只要我们能获得新的"健康"，错误（何时停止在这个递归循环中），输入部分，但我把这个留给了读者！
我也发现这个问题很有趣！
将问题建模为图可以保证最优解。图中的每个节点（顶点）表示每种剩余成分的数量列表，而每条边表示根据其中一个反应公式对成分数量的调整。
要找到具有最多健康药剂的节点，请对图执行图遍历，例如深度优先搜索（DFS）。
对于每个节点，如果没有足够的成分来进行任何反应，则返回制作的健康药剂的计数。否则，如果节点是非终端的，则执行每个有效的反应，并返回其中哪一个最终会产生最多的健康药剂。
memo查找表可以用来避免重新评估节点，从而大大加快了算法的速度。
以下是一个使用递归作为隐式堆栈（执行DFS）的相关片段：
def max_potions(ingredients, memo={})
# get all available reactions as a list
reactions = get_reactions(ingredients)
# if no reactions are possible, return
# the number of health potions made
return ingredients[:hp] if reactions.empty?
# try every possible reaction for this set
# of ingredients and determine the maxiumum
maximum = 0
reactions.each do |reaction|
key = reaction.hash
# retrieve this node's value if already visited
if memo.include?(key)
result = memo[key]
else # calculate and save the node's value
result = max_potions(reaction, memo)
memo[key] = result
end
# update the maximum as necessary
maximum = result if result > maximum
end
return maximum
end
请参阅GitHub要点，了解一个有效但基本的版本。