CONTEST ID : 1461 - 暑期算法训练 之 贪心的本质

贪心算法
贪心算法总是做出当前最好的选择，期望通过局部最优选择得到全局最优的解决方案。
贪心算法正是“活在当下，看清楚眼前”的算法，从问题的初始解开始，一步步地做出当前最好的选择，
逐步逼近问题的目标，尽可能得到最优解：即使得不到最优解，也可以得到最优解的近似解。

当然，贪心算法在解决问题的策略上看似“目光短浅”，只根据当前已有的信息做出选择，
而且一但做出选择 ，则不管将来有什么结果，都不会改变。换言之，贪心算法并不是从整体最优来考虑的，
它所做出的选择只是某种意义上的局部最优。对许多问题都可以使用贪心算法得到整体最优解或者最优解的近似解。
因此贪心算法正在生活，生产中得到大量的应用 

贪心的本质
我们在遇到具体问题时，往往分不清对哪些问题可以用贪心算法，对哪些问题不可以用贪心算法。
实际上，如果问题具有两个特性:贪心选择性质和最优子结构性质，则可以用贪心算法。

(1)贪心选择性质。贪心选择性质指原问题的整体最优解可以通过一系列局部最优的选择得到。 
应用同一规则，将原问题变为一个相似的、但规模更小的子问题，而后的每一步都是当前最优的选择。
这种选择依赖于已做出的选择，但不依赖于未做出的选择。
运用贪心算法解决的问题在程序的运行过程中无回溯过程。
(2)最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
问题的最优子结构性质是该问题是否可以用贪心算法求解的关键。例如原问题 ：
S={a1,a2,....a.....an}，通过贪心选择选出一个当前最优解{(a}之后,转化为求解子问题S-{a}， 
如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。
原问题：S={a1,a2,....a.....an}
子问题：ai  s-{ai}
贪心算法的求解步骤如下。
(1)贪心策略。指确定贪心策略，选择当前看上去最好的一个。
比如挑选苹果，如果你认为个头大的是最好的，那么每次都从苹果堆中拿一个最大的作为局部最优解，
贪心策略就是选择当前最大的苹果。如果你认为最红的苹果是最好的，
那么每次都从苹果堆中拿一个最红的，贪心策略就是选择当前最红的苹果。因此根据求解目标的不同，
贪心策略也会不同。
(2)局部最优解。指根据贪心策略，一步步地得到局部最优解。比如第1次选一个最大的
苹果放起来，记为a;第2次再从剩下的苹果中选择一个最大的苹果放起来，记为a2，以此类推。
(3)全局最优解。指把所有的局部最优解都合成原问题的一个最优解{(a,a2......}。

SERVER TIME : 2026-09-11 15:18:23
Running Left 671days 21 hours 41 minutes 37 seconds

STATUS : Running    OPEN : Public
Start Time : 2026-07-14 09:00:00
End Time : 2028-07-14 13:00:00