硬币改变算法JS-Java 学习之路

我一直试图为这个算法提出一个解决方案3-4天，但似乎没有任何效果，可用的解决方案对我来说更先进 . 它必须通过条件解决，因此不需要递归或动态编程 .

鉴于以下面额，我需要确定给出变化所需的最少硬币数量：1,0.5,0.2,0.1,0.05,0.02和0.01 .

输入如下：

物品的价格

由客户支付的金额

目前的想法：

let price = +gets();
let paidSum = +gets();
//gets is used to accept number input
let change = paidSum - price;

我想我可以使用Math.floor来隔离整数部分并减去它，但后来我不知道如何处理剩余的总和 .

模数是否可以测试剩余的和是否包含任何剩余的变化值，然后再次减去直到我达到零？

我确实意识到这不是最好的问题，但我在这里不知所措，除此之外我还完成了其他任务 . 谢谢 .

1 回答

使用您指定的面额，问题比一般change making problem更简单 . 在这个实际案例中，我们可以确定使用最大面额（不大于支付金额）总是会产生最佳解决方案 .

因此，不需要递归或动态编程 . 只需一个简单的循环即可 .

我将在这里忽略获得账单价格和客户支付金额的额外“层” . 最后，唯一重要的是回报客户的变化金额 . 因此，此片段要求更改金额并返回需要作为更改提供的硬币 .

function getChange(amount) {
    amount *= 100; // Convert to number of cents
    var denominations = [1, 2, 5, 10, 20, 50, 100]; // cents
    var result = [];
    while (amount > 0) {
        var coin = denominations.pop(); // Get next greatest coin
        var count = Math.floor(amount/coin); // See how many times I need that coin
        amount -= count * coin; // Reduce the amount with that number of coins
        if (count) result.push([coin/100, count]); // Store count & coin
    }
    return result;
}

// I/O management

change.oninput = function () {
    var coins = getChange(this.value);
    result.textContent = coins.map(([coin, count]) => `${count} x $${coin}`).join(" + ");
};

To be paid to customer: <input id="change">
<div>Coins to pay: <span id="result"></span></div>

回复于 2024-04-28T01:38:58+08:00

硬币改变算法JS

1 回答

相关问题