JavaScript-这种硬币兑换算法有什么问题

Question

我试图使用贪婪算法来计算在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变量，该变量显示已调度的更改量。我还将创建一个数组变量，该变量将保存某个硬币的分配次数。

为此，我将迭代coins数组并将所有值设置为0。如果我不知道不同硬币价值的数量，这一点很重要

接下来，我考虑设置一个while条件，检查金额是否已达到

如果没有，我将启动一个for循环，迭代所有硬币值。对于贪婪算法，随着索引的增加，硬币的价值降低。这是使用尽可能少的硬币

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

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

我期望的结果是

[2,1,1,0,2]

这意味着2个50美分，1个25美分，1个10美分和2个便士

在这个函数中，它应该表示dispatched的值，即返回值。运行上述代码时，我没有得到返回值

我能得到的唯一解释是我用错了循环。即使经过检查我也看不出来

我错过了什么。见解受到极大赞赏

Answer 1

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

此外，第一个尝试在调度数组中放置零的循环为数组索引提供了错误的变量。

因此，您可以尝试以下方法：

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 ]

Answer 2

显然，变量sum初始化为0，并且从未更新，因此循环

while (sum < total)

将永远运行，因为总计增加，但从未减少。也许您想更新和而不是总计。我猜你已经混淆了和（显然是已经被选择的硬币覆盖的值）和总计的语义学，这是函数的参数。