With certain combinations of currency, the greedy strategy won't work so well. Imagine you need to give 30 cents change, using US coins but not nickels. The intuitively "correct" solution is three dimes, but the greedy strategy will give one quarter and five pennies. If you want to define the greedy answer to be the correct one, that's fine, but you didn't make that clear in the problem statement.
If the coins are a little stranger, the greedy strategy will fail altogether. Maybe the land of Frobozz has 2-frob and 3-frob coins, but no 1-frob coin. You can make 7 frobs with one 3 and two 2s, but if you start out by giving two 3s, you're stuck.
We could define a "generalized penny" to be a coin which every other coin is a multiple of. The penny and the yen are both "pennies" by this definition. If such a coin exists, the greedy method will always produce an answer. There's no frob-penny in my example, though.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|
