贪心算法是一类构造性算法，它在求解最优化问题的过程中始终只做局部最优的选择，并且不在以后对已经做出的选择进行回溯或修改。使用贪心算法需要证明局部最优解等于全局最优解。

贪心可以说是算法的基础，几乎所有算法都蕴含了贪心的思想。同时，贪心更多是一种思想而不是具体的算法，且常常与别的算法配合使用，但也有如反悔贪心这种易单独出现的较为固定的套路，实际训练中更多以多刷题总结经验为主，这里重点讲解一下反悔贪心。

知识点

  • 贪心算法不能保证对所有问题都得到全局最优，除非你只是用于骗分，否则必须进行验证
  • 在内容是无序的时候，我们常常会进行一下排序之后进行贪心
  • 思考贪心时往往先从直觉出发，然后通过反证法证明没有解法更优或者可以通过反悔贪心进行修正

反悔贪心

反悔贪心（也称为可反悔的贪心、反悔贪心算法）是一种改进的贪心算法策略，它在传统贪心算法的基础上增加了“反悔”机制，从而在某些问题上能得到更优的解。核心思想是传统贪心算法每一步都做出当前最优选择，且不可更改。而反悔贪心允许我们在后续步骤中撤销之前的选择，替换为更优的决策，从而修正可能产生的局部最优错误。

实际运用中通常将当前的最优解先当作全局最优解，且使用优先队列记录做过的选择，当之后有更好的选择时，替换当前队列中最不优的操作。

# 贪心算法 # 算法
Logo
天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

avatar 天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

avatar 天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

avatar 天工造物局