3

我正在尝试使用贪婪算法来计算达到 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 循环中嵌套一个 while 循环。这个 while 循环将检查最大的硬币是否仍然可以使用。

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

我期待的输出是这个

[2,1,1,0,2]

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

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

我能得到的唯一解释是我使用错误的循环。即使在检查时我也看不到

我在这里想念什么。非常感谢您的见解

4

2 回答 2

3

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

while (sum < total)

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

于 2016-03-08T07:22:33.223 回答
1

您不需要嵌套循环。相反，您可以在每一步简单地进行整数除法，方法是除法然后使用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 ]
于 2016-03-08T07:38:43.937 回答