前端算法·专项攻破十：贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。它是一种在每一步选择中都采取最优解的策略，最终希望达到全局最优解。
贪心算法的特点是每一步都采取最优解，因此它通常可以在每一步都得到局部最优解，从而希望得到全局最优解。然而，贪心算法并不总是能够得到全局最优解，因为问题的特性可能使得每一步的最优解并不等于全局的最优解。
贪心算法的适用场景通常是那些可以通过局部最优解来得到全局最优解的问题。例如，在找零问题中，我们可以每次选择面值最大的硬币，从而在有限次数的选择中得到零钱总数最多的组合。再比如在最小生成树问题中，我们可以采用Kruskal算法或Prim算法，从边的角度入手，每次选择权值最小的边，从而得到权值最小的生成树。
下面是一个使用贪心算法解决找零问题的示例代码：

function greedyChange(money) {
const denominations = [100, 50, 20, 10, 5, 1];
const result = [];
for (let i = 0; i < denominations.length; i++) {
while (money >= denominations[i]) {
result.push(denominations[i]);
money -= denominations[i];
}
}
return result;
}

在这个示例中，我们定义了一个greedyChange函数，它接受一个整数参数money，表示需要找零的总金额。我们定义了一个硬币面值的数组denominations，其中包含了不同面值的硬币。然后，我们使用一个循环来依次尝试使用每种面值的硬币进行找零，只要当前金额能够被当前硬币面值整除，我们就将该硬币加入到结果数组中，并从总金额中减去该硬币的面值。最后，返回结果数组即可。
贪心算法的优点在于其简单、直观、易于实现，而且往往能够在实践中得到不错的结果。但是，贪心算法也存在一些缺点，例如它并不能保证得到全局最优解，而且对于一些问题可能存在性能瓶颈。因此，在使用贪心算法时需要注意其适用场景和限制条件。
总的来说，贪心算法是一种非常实用的算法思想，它可以解决很多实际问题。但是，我们也需要了解其适用场景和限制条件，并在实践中灵活运用贪心算法和其他算法思想来解决问题。