我正在尝试使用贪心算法计算在JavaScript中达到金额所需的最小硬币数量
返回结果将是一个由每个级别的硬币数组成的数组
我决定创建一个可以解决这个问题的函数,但它不起作用
window.addEventListener('load', function(e) {
function calculateChange(coins, total) {
var sum = 0;
var dispatched = [];
for (var i = 0; i < coins.length;i++) {
dispatched[c] = 0;
}
while (sum < total) {
for (var c = 0; c < coins.length; c++) {
while (total - sum >= coins[c]) {
total += coins[c];
dispatched[c]++;
}
}
}
return dispatched;
}
alert(calculateChange([50,25,10,5,1],137));
}, false);
calculateChange函数接受两个参数,一个硬币值数组和金额 .
第一步是初始化一个sum变量,该变量显示已经分派的变化量 . 我还将创建一个数组变量,它将保存某个硬币的分配次数 .
为此,我将迭代硬币数组并将所有值设置为0.如果我不知道不同硬币值的数量,这很重要
接下来我想到了一个检查是否达到金额的条件
如果没有,我将启动一个迭代所有硬币值的for循环 . 对于贪婪算法,随着指数增加,硬币值减小 . 这是使用尽可能少的硬币
为了防止向下跳转硬币层次结构,将在此for循环中嵌套一个while循环 . 这个while循环将检查是否仍然可以使用最大的硬币 .
如果不满足循环条件,则while循环结束 . for循环将通过递增索引继续 . 我们将下移到下一个较低级别的硬币 . 这个过程将重复进行
我期待的输出就是这个
[2,1,1,0,2]
这意味着2 50s,1 1/4,1角钱和2便士
在此函数中,这应该表示dispatched的值,即返回值 . 运行上面的代码,我没有得到返回值
我可以解释的唯一解释是我使用了错误的循环 . 即使经过检查,我也看不到它
我在这里想念的是什么深刻的见解非常感谢
2 回答
显然,变量
sum
用0
初始化并且从不更新,所以循环将永远运行,因为
total
增加了,但从未减少 . 也许你想更新sum
而不是total
. 我猜你已经混淆了sum
的语义(显然是已经用所选硬币覆盖的值)和total
,这是函数的参数 .您不需要嵌套循环 . 相反,您可以通过划分然后使用
Math.floor()
在每一步执行整数除法 . 这将为您提供当前面额所需的硬币数量,然后您可以根据该数量减少剩余总数 .另外,尝试将零放入
dispatched
数组的第一个循环对数组索引具有错误的变量 .所以你可能会尝试这样的事情: