Skip to content

贪心算法

一句话解释

贪心算法每一步都做出当前看来最优的选择,期望最终得到全局最优解。

用大白话说

贪心算法逐步构造解,每步都选择当下看起来最好的选项(局部最优),且从不回溯。当问题具备合适的结构(贪心选择性质与最优子结构)时,这种局部策略能产生全局最优解。经典贪心问题包括找零钱(优先选最大面额)、活动选择(选最早结束的活动)、哈夫曼编码(合并两个频率最低的符号)、Dijkstra 最短路径(始终扩展最近的未访问节点)。Kruskal 与 Prim 的最小生成树算法也是贪心。贪心算法简单快速,但并非适用于所有问题。有些问题中,早期的贪心选择会阻断更优的整体解。当贪心失效时,需要动态规划或回溯。证明贪心算法正确,通常要说明不存在与贪心选择相矛盾的更优解。

示例

javascript
// 找零钱——贪心:尽量使用最大面额
function greedyCoinChange(amount, coins) {
  coins.sort((a, b) => b - a); // 降序
  const result = [];
  for (const coin of coins) {
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }
  return result;
}

console.log(greedyCoinChange(63, [25, 10, 5, 1]));
// [25, 25, 10, 1, 1, 1] — 6 枚硬币

贪心策略总是取能放下的最大面额。对美国标准硬币,这能得到最优硬币数。

相关术语

相关资源

相关课程

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回术语表