硬币兑换算法JS

Question

我已经尝试为这个算法想出一个解决方案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来分离整数部分并减去它，但我不知道如何处理剩余的和。

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

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

Answer 1

更简单，反转并映射以美分为单位的面额，并返回一个新的数组，其中包含每个面额所需的硬币数量。

const coinsCents = [1, 2, 5, 10, 20, 50, 100]
const getChange = (amountInCents) => {
return coinsCents.reverse().map(coin => {
let amountCoin = Math.floor(amountInCents/coin)
amountInCents -= amountCoin * coin
return amountCoin
}).reverse()
}

Answer 2

使用您指定的面额，这个问题比一般的更改问题更简单。在这种实际情况下，我们可以确信，使用最大面额，即不大于支付金额，总是会得到最佳解决方案。

因此，不需要递归或动态编程。只要一个简单的循环就可以了。

在这里，我将忽略获取账单价格和客户支付金额的额外"层"。最后，唯一重要的是要偿还给客户的零钱金额。因此，这个片段要求兑换金额，并返回需要兑换的硬币。

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>

Answer 3

var coins;
var coinArray = {};
var output = {};

/* Method to get coin value without decimal point - it is required because 
* javascript will consider 5.6 as 6 if we do Math.round()
*/
function getRoundFigureCoinValue(x) {
return (x * 10 - ((x * 10) % 10)) / 10;
}
// Method to calculate possible combination of coins
function calculateCoins(input) {
let largestPossibleCoin = 1;
if (input) {
coins.forEach((x) => {
if (input >= x) {
largestPossibleCoin = x;
}
});
let remainingCents = input % largestPossibleCoin;
output[largestPossibleCoin] = getRoundFigureCoinValue(
(input / largestPossibleCoin).toFixed(1)
);
if (remainingCents && input > 1) {
calculateCoins(remainingCents);
}
return largestPossibleCoin;
}
}
// Method to be called to get output.
function calculatePossibleCoinCombinations(value) {
if (isNaN(value) || +value <= 0) {
console.log('Invalid input');
return;
} else {
console.log('Possible combinations are:')
value = +value;
}
coins = [1, 5, 10, 25];
while (coins.length) {
let largestPossibleCoin = calculateCoins(value) || 0;
let outputString = '';
coins = coins.filter((x) => x < largestPossibleCoin);
Object.keys(output).forEach((key) => {
outputString += `${output[key]} - ${key} cents; `;
})
console.log(outputString);
output = {};
}
}

/*
Sample inputs:
calculatePossibleCoinCombinations('89');
calculatePossibleCoinCombinations(10);
calculatePossibleCoinCombinations(0);
calculatePossibleCoinCombinations('someString');
calculatePossibleCoinCombinations(-10)
*/