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变量，它显示已经派发的找零金额。我还将创建一个数组变量，它将保存某个硬币已被分配的数量。

为此，我将遍历硬币数组并将所有值设置为0。如果我不知道不同硬币值得数量，这一点非常重要。

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

如果没有，我将开始一个for循环，它迭代所有硬币值。对于贪心算法，随着索引增加，硬币值减少。这样可以使用尽可能少的硬币。

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

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

我期望的输出是这样的。

[2,1,1,0,2]

这表示有2个50美分，1个25美分，1个10美分和2个1美分。

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

唯一可能的解释是我使用循环方式不对。即使仔细检查，我也看不出来。

我错过了什么？非常感谢提供见解。

- user5680735

---

如果期望的输出是 [2,1,1,0,2]，那么实际的输出是什么？还是存在某个无限循环？ - Codor

可能是一个无限循环。我没有得到一个令人惊讶的返回值。 - user5680735

Answer 1

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

while (sum < total)

本段代码可能会一直运行下去，因为total虽然一直在增加却从来没有被减少过。也许你想要更新的是sum而不是total。我猜你把sum（显然是已选择硬币的价值总和）和total（函数的参数）的语义搞混了。

- Codor

---

我相信这就是原因。我混淆了变量名，特别是sum和total。这就是没有描述性变量名的问题之一。它可能会导致这种混淆。 - user5680735

好的，循环问题已经解决了。但是现在输出是NaN，NaN，NaN，NaN。这与我的初始for循环有关。如果我删除它并硬编码它，那么它可以工作，但是如果我不知道可能的硬币价值数量，该怎么办呢？ - user5680735

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 ]

- Michael Geary