Supposedly Trivial math question.
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.
More information about the PLUG