title: Coin changing algorithm
body: <p>Suppose I have a set of coins having denominations a1, a2, ... ak.</p>
  
  <p>One of them is known to be equal to 1.</p>
  
  <p>I want to make change for all integers 1 to n using the minimum number of coins.</p>
  
  <p>Any ideas for the algorithm.</p>
  
  <pre><code>eg. 1, 3, 4 coin denominations
  n = 11
  optimal selection is 3, 0, 2 in the order of coin denominations.
  
  n = 12
  optimal selection is 2, 2, 1.
  </code></pre>
  
  <p>Note: not homework just a modification of <a href="http://en.wikipedia.org/wiki/Change-making_problem" rel="nofollow noreferrer">this</a> problem</p>