在紅寶石中使用配料和配方轉換來優化藥水釀造計劃？

Question

下面是我解決這個問題：

「三個女巫在哈姆雷特可以釀造任何藥水前提是擁有 正確的成分假設五個成分 有必要做一個健康的藥水：蠑螈眼（EON），蛙的趾（TOF）， 蝙蝠（WOB），加法器的叉（AF）的羊毛，和狼（絲束）的齒四種反應 可以>這些成分之間發生：

4 EON + 2 wob = 3 af + 4 tow
3 tow + 1 tof = 2 eon
1 WOB + 2 AF = 1 TOF
4 TOF + 7絲束+ 2 AF = 1健康藥水

假設可以控制反應的順序，寫一個程序， 可以計算健康藥水一個的最大數量可以用 沖泡成分。這裏有一個例子：如果我有34 eon， 59 tof，20 wob，5 af和20 tow，我可以製造7種健康藥水。「

摘錄：Ophir Frieder，Gideon Frieder和David Grossman。 「用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.\n\n" 

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 "\n\nMade #{potion} potion(s).\n\n" 

for name in ingredients.keys 
puts "You have " + ingredients[name].to_s + " " + name + " left.\n" 
end  

總之，這就是「整潔的」我能想出如何解決這個問題。我認爲我正確地命令了轉換，以便在製作魔藥時不會出現任何低效率。我通過書中示例的輸入獲得了期望的結果。

任何人都可以證實它確實好像/我不錯過一些可以進一步最大化我的藥水的主要優化？我找不到第三次轉換（1wob + 2af = 1tof）。

謝謝！

Answer 1

有趣的問題！

所以讓我們來重述一下：目標是計算「健康」藥水，並且如果此藥水的任何成分缺失，可以找到可用於創建缺失成分的其他藥水。

這聽起來是一個遞歸算法。首先，讓我們模擬「創造魔藥」問題。

假設e有一個藥水公式，所有需要的成分（負值）的哈希值以及由此產生的初始正值。

例如：

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 

名單現在，有一些小細節，比如主迴路（我們需要繼續只要我們能得到新的「健康」，錯誤（何時停止在這個遞歸循環），輸入部分，但是我離開了這個給讀者！