贪心算法-js

贪心算法（Greedy Algorithm）是一种常见的算法思想，通常用于求解最优化问题，它每一步都选择最优解，从而希望最终得到全局最优解。

在Javascript中，我们可以使用贪心算法来解决一些问题，例如找零钱、任务调度、背包问题等。下面是一个找零钱的例子，我们假设有一些货币面值，比如[1, 5, 10, 20, 50, 100]，以及一个要找零的金额amount，我们希望找出最少的货币数来凑出amount。

function findMinCoins(coins, amount) {
  coins.sort((a, b) => b - a); // 将货币面值从大到小排序
  let numCoins = 0;
  for (let i = 0; i < coins.length; i++) {
    while (amount >= coins[i]) { // 不断选择面值最大的货币
      amount -= coins[i]; // 减去已经选择的货币面值
      numCoins++; // 增加选择的货币数
    }
  }
  return numCoins;
}

let coins = [1, 5, 10, 20, 50, 100];
let amount = 123;
let numCoins = findMinCoins(coins, amount);
console.log(numCoins); // 输出结果：4

在这个实现中，我们首先将货币面值从大到小排序，然后从大到小扫描每一种面值的货币，每次选择尽可能多的这种面值的货币，直到凑出了所需的金额amount为止。这样，我们就得到了最少的货币数来凑出amount。

需要注意的是，贪心算法并不是万能的，只适用于一些特定的问题。如果问题没有具备贪心选择性质，则贪心算法可能得不到最优解。