title: Algorithm for planning the creation of an object from dependencies
body: <p>I am an alchemist. I can make things out of other things according to my recipe book. For instance:</p>
  
  <pre><code> 2 lead + 1 bismuth -&gt; 1 carbon
   1 oxygen + 5 hydrogen + 3 nitrogen -&gt; 2 carbon
   5 carbon + 5 titanium -&gt; 1 gold
   ...etc.
  </code></pre>
  
  <p>My recipe book contains thousands of recipes, each of which consumes some discrete amount of one or more inputs and produces a discrete amount of one output. Being a lazy alchemist, I don't want to remember all my recipes. I want to write a computer program to solve this problem for me. The input to the program is a description of what I want, like "2 gold", and a description of what I have in stock, like "5 titanium, 6 lead, 3 bismuth, 2 carbon, 1 gold". The output should be either "cannot be made" or a sequence of instructions for creating the thing. For the example given here, the output could be:</p>
  
  <pre><code>make 2 carbon out of 4 lead + 2 bismuth
  make 1 gold out of 4 carbon + 4 titanium
  </code></pre>
  
  <p>Then, combined with the 1 gold I already have, I have the 2 gold I wanted.</p>
  
  <p>One last note: the recipes are weighted; e.g. I prefer to make carbon out of lead and bismuth if I can.</p>
  
  <p>Is there an elegant way to formulate and solve this problem? A naive recursive solution looks tempting, but I can think of recipe sets that would cause it to do an exponential amount of work.</p>
  
  <p>(And, as a followup, someday my research might uncover a circular set of recipes---maybe I can make 1 hydrogen out of 1 helium and 1 helium out of 1 hydrogen---and I would like to be able to handle this case as well.)</p>