Javascript 贪心算法带来改变

Question

我正在研究经典的“进行更改”问题，该问题在许多其他语言中都有详细记录，但在 Javascript 中却没有太多相关内容。到目前为止，我有这个:

    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);

但是，这看起来非常重复，而且我发现对于某些值来说，这是很便宜的。怎样才能让它更准确、更简洁呢？

Answer 1

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

可能是由于floating-point issues 。而且您不应该使用 parseInt 来转换数字 - 它适用于字符串。

this seems awfully repetitive

具有代表不同硬币的数据结构的循环会有所帮助。您已经对结果做了类似的操作:coins 是一个数组，而不是 4 个不同的变量。

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);