贪心算法
一句话解释
贪心算法每一步都做出当前看来最优的选择,期望最终得到全局最优解。
用大白话说
贪心算法逐步构造解,每步都选择当下看起来最好的选项(局部最优),且从不回溯。当问题具备合适的结构(贪心选择性质与最优子结构)时,这种局部策略能产生全局最优解。经典贪心问题包括找零钱(优先选最大面额)、活动选择(选最早结束的活动)、哈夫曼编码(合并两个频率最低的符号)、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 枚硬币贪心策略总是取能放下的最大面额。对美国标准硬币,这能得到最优硬币数。
相关术语
相关资源
相关课程
- 算法
学习贪心算法。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。