Javascript Greedy Algorithm Making Change

Question

I'm working on the classic "making change" problem, which is highly documented in plenty of other languages, but there's not much out there for it in Javascript. So far, I have this:

    var total = $('#total').val();
    var coins = [];

    function makeChange(total, coins) {     
        var remainder = 0;

        if (total % 0.25 < total) {
            coins[3] = parseInt(total / 0.25);
            remainder = total % 0.25;
            total = remainder;
        }

        if (total % 0.10 < total) {
            coins[2] = parseInt(total / 0.10);
            remainder = total % 0.10;
            total = remainder;
        }

        if (total % 0.05 < total) {
            coins[1] = parseInt(total / 0.05);
            remainder = total % 0.05;
            total = remainder;
        }

        coins[0] = parseInt(total / 0.01);
    }

    function showChange(coins) {
        if (coins[3] > 0) {
            $('.quarter').html(coins[3] + " quarter(s).");
        }

        if (coins[2] > 0) {
            $('.dime').html(coins[2] + " dime(s).");
        }

        if (coins[1] > 0) {
            $('.nickel').html(coins[1] + " nickel(s).");
        }

        if (coins[0] > 0) {
            $('.penny').html(coins[0] + " pennies.");
        }
    }

    makeChange(total, coins);
    showChange(coins);

However, this seems awfully repetitive and I'm finding that with certain values, it's a penny off. How can I make it more accurate and concise?

I'm finding that with certain values, it's a penny off. examples? — Matt Burland
– Matt Burland, Commented Sep 8, 2014 at 18:34
There is something wrong with his code so it's fine here. Example 2.21 — user1071777
– user1071777, Commented Sep 8, 2014 at 18:40
@TheMuffinMan: Read the help center on those three sites and you'll see the differences: programmers, so, cr. If you have a specific question about a bug in code, then SO is the right place. If you have code that works, but want to know how to make it better, hit CR. If you have a general question about programming concepts, design, algorithms or similar, then programmers is the right place. — Matt Burland
– Matt Burland, Commented Sep 8, 2014 at 19:25

Bergi · Accepted Answer · 2014-09-08 19:16:24Z

4

I'm finding that with certain values, it's a penny off.

Probably due to floating-point issues. And you shouldn't use parseInt to convert a number - it's meant for strings.

this seems awfully repetitive

A loop, with a data structure that represent the different coins will help. You already did something like that for your result: coins is an array, not 4 different variables.

function makeChange(total, values) { 
    var coins = [],
        epsilon = 1e-5; // this is wrong in general!
    // assume values are ascending, so we loop backwards
    for (var i=values.length; i--; ) {
        coins[i] = Math.floor(total / values[i].val + epsilon);
        total %= values[i].val;
    }
    return coins;
}

function showChange(coins, values) {
    for (var i=values.length; i--; ) {
        var el = $(values[i].sel);
        if (coins[i] > 0) {
            el.html(coins[i] + " "+values[i].name+".");
        } else {
            el.empty();
        }
    }
}

var values = [
    {val:0.01, sel:'.penny', name:"pennies"},
    {val:0.05, sel:'.nickel', name:"nickel(s)"},
    {val:0.10, sel:'.dime', name:"dime(s)"},
    {val:0.25, sel:'.quarter', name:"quarter(s)"}
];
showChange(makeChange(parseFloat($('#total').val()), values), values);

edited Sep 8, 2014 at 19:16

answered Sep 8, 2014 at 18:41

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Harlow Over a year ago

this is great. much more efficient than what i had going. i'm still coming up with errors every once and while with different values - like .45 returned 2 quarters and 2 dimes.

Bergi Over a year ago

@Harlow: You're right, my use of Math.round was a mistake (it rounded up not only very-near values, fixed now by using epsilon and floor); also the comparison done in the if-statement was still flawed. I just omitted it now…

Bergi Over a year ago

For getting around these awful things, you may want to use integers like @MattBurland did. See floating-point-gui.de/formats/integer

Matt Burland · Accepted Answer · 2014-09-08 19:33:23Z

0

Your best bet to avoid rounding problems is to just multiple your total by 100 to convert your dollar amount into all pennies, then do you conversion. For example:

function makeChange(total, coins) {
    var remainder = 0;
    total = Math.round(total * 100);

    coins[3] = Math.floor(total / 25);
    remainder = total - coins[3] * 25;
    total = remainder;

    coins[2] = Math.floor(total / 10);
    remainder = total - coins[2] * 10;
    total = remainder;

    coins[1] = Math.floor(total / 5);
    remainder = total - coins[1] * 5;
    total = remainder;

    coins[0] = total;
}

http://jsfiddle.net/t14cwdph/4/

For making your code easier to manage - see @Bergi's answer.

edited Sep 8, 2014 at 19:33

answered Sep 8, 2014 at 19:12

Matt Burland

45.3k18 gold badges110 silver badges182 bronze badges

2 Comments

Bergi Over a year ago

The first Math.floor (around total * 100) does need to be a Math.round, though!

Bergi Over a year ago

No. Your dollars are still floating point numbers - try Math.floor(0.29*100)!

Collectives™ on Stack Overflow

Javascript Greedy Algorithm Making Change

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related