Supposedly Trivial math question.

Steve Meyers steve at plug.org
Tue Oct 1 10:44:14 MDT 2013


On 10/1/13 10:30 AM, Lonnie Olson wrote:
> On Tue, Oct 1, 2013 at 10:28 AM, Steve Meyers <steve at plug.org> wrote:
>> On 10/1/13 10:24 AM, Adam Stevenson wrote:
>>>
>>> $bills = array(100, 50, 10, 5, 1, 0.50, 0.25, 0.05, 0.01); // Sorted
>>
>>
>> You forgot $20 bills, and $2 bills for that matter.
>
> Yes, but the problem stated specifically to not specify any upper
> limit on bill size.  Also this constraint seems to indicate that it is
> not necessarily using standard US denominations.

If we're using other denominations, this algorithm could run into 
trouble.  I believe it would only occur when one bill is more than 50% 
of the value of the bill above it.

As an example, if there was a $3 bill, then $9 would be best served by 
3x$3, while this algorithm would give 1x$5 + 4x$1.

Steve


More information about the PLUG mailing list