JS使用贪心算法解决找零问题示例

首先，让我们了解一下什么是贪心算法。贪心算法（Greedy algorithm）在每一步选择中都采取在当前状态下最优的选择，从而希望导致结果是全局最优的算法。在找零钱的问题上，贪心算法指的是在找零过程中，每次选取最大的面额进行找零。以下是使用JS实现贪心算法解决找零问题的步骤：

1. 排序

对于现金支付金额和硬币面额数组，我们可以先对硬币面额数组进行从大到小的排序。这是因为贪心算法要求我们每次选取最大面额进行找零。

1. 找零

接下来我们可以开始找零。对于当前需要找零的面额，从大到小遍历已经排好序的硬币面额数组，每次选取可以匹配完整硬币个数最大的面额，直到找完为止。

下面是一个简单的实例，以5，2，1分硬币找零为例：

function getChange(amount, coins) {
  var result = []; // 用于保存找零结果
  coins.sort((a, b) => b - a); //按照面额从大到小排序
  for (let i = 0; i < coins.length; i++) {
    const coin = coins[i];
    while (amount >= coin) { //只要需要找零的总额大于当前面额
      result.push(coin); //将该面额加入结果
      amount -= coin; //更新需要找零的总额
    }
  }
  return result;
}

console.log(getChange(11, [5, 2, 1])); //输出 [5, 5, 1]
console.log(getChange(8, [5, 2, 1])); //输出 [5, 2, 1]

以上代码中，我们首先将硬币面额数组按照面额从大到小排序，然后使用while循环不断地从大到小遍历已经排好序的硬币面额数组，每次选取可以匹配完整硬币个数最大的面额，并将该面额加入结果中，直到找完为止。

下面是另一个示例，以美元找零为例：

function getChange(amount) {
  const bills = [100, 50, 20, 10, 5, 1]; //美元的面额数组
  const result = {}; //用于保存找零结果
  for (let i = 0; i < bills.length; i++) { 
    const bill = bills[i];
    while (amount >= bill) { //只要需要找零的总额大于当前面额
      result[bill] = result[bill] ? result[bill] + 1 : 1; //将该面额加入结果
      amount -= bill; //更新需要找零的总额
    }
  }
  return result;
}

console.log(getChange(137)); //输出 {100: 1, 20: 1, 10: 1, 5: 1, 1: 2}
console.log(getChange(53)); //输出 {50: 1, 1: 3}

在以上代码中，我们将美元面额数组按照从大到小的顺序排列，并使用while循环不断地从大到小遍历已经排好序的美元面额数组，每次选取可以匹配完整美元个数最大的面额，并将该面额加入结果中，直到找完为止。

希望以上两个示例可以帮助你更好地理解如何使用JS实现贪心算法解决找零问题。