JavaScript

Question

我正在尝试使用贪心算法来计算达到 JavaScript

中的金额所需的最少硬币数量

return结果将是一个数组，其中包含每个级别的硬币数量

我决定制作一个函数来解决这个问题，但它不起作用

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。如果我不知道不同硬币值的数量，这很重要

接下来我想到了一个 while 条件来检查是否已经达到金额

如果没有，我将启动一个循环遍历所有硬币值的循环。至于贪心算法，随着指数的增加，币值下降。这是为了尽量少用硬币

为了防止跳下硬币层次结构，将在这个 for 循环中嵌套一个 while 循环。这个while循环会检查最大的硬币是否还可以使用。

如果不满足循环条件，while循环结束。 for 循环将通过递增索引继续。我们将向下移动到下一个较低级别的硬币。该过程将重复

我期待的输出是这样的

[2,1,1,0,2]

这意味着 2 个 50 分、1 个季度、1 个角钱和 2 个便士

在这个函数中，this应该代表dispatched的值，也就是return值。运行上面的代码，我没有得到一个return值

我能得到的唯一解释是我使用了错误的循环。检查了也没看出来

我在这里错过了什么。非常感谢见解

Answer 1

显然，变量 sum 是用 0 初始化的，并且从未更新过，所以循环

while (sum < total)

将永远运行，因为 total 会增加，但不会减少。也许您想更新 sum 而不是 total。我猜你混淆了sum（显然是所选硬币已经覆盖的值）和total的语义，后者是函数的参数。

Answer 2

您不需要嵌套循环。相反，您可以通过除法然后使用 Math.floor() 在每一步简单地进行整数除法。这给了你当前面额所需的硬币数量，然后你可以在此基础上减少剩余的总数。

此外，您的第一个循环尝试将零放入 dispatched 数组，但数组索引的变量有误。

所以你可以尝试这样的事情：

function calculateChange( coins, total ) {
    var dispatched = [];
    for( var i = 0;  i < coins.length;  i++ ) {
        dispatched[i] = 0;
    }

    for( var c = 0;  total > 0;  c++ ) {
        dispatched[c] = Math.floor( total / coins[c] );
        total -= dispatched[c] * coins[c];
    }
    return dispatched;
}

console.log( calculateChange( [50,25,10,5,1], 137 ) );
// logs [ 2, 1, 1, 0, 2 ]

JavaScript - 这个硬币找零算法有什么问题

JavaScript - What's wrong with this coin change algorithm

algorithm

loops

greedy

coin-change