<p>Actually this problem has been studied as <strong>Canonical coin systems</strong>, and we even got a paper about how to determine whether a given coin system can support a greedy solution. The original paper may give you some insights: <a href="http://arxiv.org/pdf/0809.0400.pdf" rel="nofollow">Canonical coin systems for change-making problems</a>.</p>

<p>Alternatively, you can google the key word "Canonical coin systems" for more information.</p>
Interview: Making change for n cents (arbitrary denominations)
<p>This question occurred as part of an increasingly-difficult problem in an interview. It started ever so simply:</p>

<blockquote>
  <p>(1) Assuming an infinite supply of coins (in the usual 1, 5, 10, 25 cent denominations). Given  <em>n</em> cents, is there always a way to make change for it using the normal denominations?</p>
</blockquote>

<p>Yes, since the penny divides all possible values of <em>n</em> cents.</p>

<blockquote>
  <p>(2) Good, now write a program that accepts <em>n</em> (positive) cents, and returns one possible way of making change for it</p>
</blockquote>

<p>Return <em>n</em> pennies.</p>

<blockquote>
  <p>(3) Smart ass. What if you want to minimize the number of coins required to make the change?</p>
</blockquote>

<p>Start with the largest denomination <em>d_i</em>, and take the maximum number of them such that you don't exceed <em>n</em>, <em>m_i</em>. Take <em>n - (d_i)(m_i)</em> and repeat for next largest denomination.</p>

<blockquote>
  <p>(4) Good, can you prove this solution is optimal?</p>
</blockquote>

<p>Yes, { blah, blah }</p>

<blockquote>
  <p>(5) Ok, *smirk* , now what if, in addition to the <em>n</em> cents, you were given an arbitrary-sized array consisting of arbitrary denominations? You can assume each denomination occurs only once in the array, and that all denominations are positive </p>
</blockquote>

<p>My initial thought was just to sort the array of denominations, and apply the same logic as in (4). Luckily, before I communicated this, I caught myself and realized it wouldn't work. But now I realized I was in a pickle.</p>

<p>My next thought was to apply the sum-subset problem to each divisor of <em>n</em>, but realized this was probably overkill. The solution I ended up providing just used the <a href="http://en.wikipedia.org/wiki/Change-making_problem" rel="nofollow">Change-making problem</a>, and short-circuited it when I found <em>some</em> solution. I feel like there has to be a smarter way of doing this though..</p>

<p>The problem reduces to: <strong>Given a finite set <em>S</em> of distinct natural numbers, find a linear combination of elements of <em>S</em> that (1) sum to another natural number <em>n</em>, (2) minimize the sum of coefficients in the lin.combination</strong></p>