<p>Some answers can be found in this article: <a href="http://arxiv.org/pdf/0801.0120v2.pdf" rel="nofollow">http://arxiv.org/pdf/0801.0120v2.pdf</a></p>

<p>(At least according to their abstract, I didn't read the whole paper)</p>
Why doesn't greedy algorithm work for some currencies that are unlike US currency?
<p>To make $6.39, you can choose:</p>

<ul>
<li>$5 bill </li>
<li>$1 bill to make $6. </li>
<li>25¢ coin, to make $6.25 </li>
<li>10¢ coin, to make $6.35 </li>
<li>Four 1¢ coins, to make $6.39.</li>
</ul>

<p>However it doesn't work if the currency has coins with weights of 1,7, and 10. My question is, why does the greedy algorithm work [efficiently] only for a few weights? What are the conditions to be satisfied for the given set of weights to satisfy the greedy algorithm <strong>and</strong> be optimal at the same time?</p>