所谓贪心，指的是在某一刻做出对于当前情况最好的行为，也就是说，贪心并不从全局最优考虑问题，而是某种意义上寻找局部最优的行为。 只是，当答案具有某些性质的时候，这种局部最优会变成全局最优：

• 最优子结构性质：原问题最优解一定包含子问题最优解（保证可以归纳（也就是推广至所有自然数N）最优子结构性，证明原问题去除贪心选择后得到的子问题也属于原问题的最优解/可化归）

• 贪心选择性质：每一步的贪心选择一定是原问题的某个最优解的一部分（保证原有策略不受冲击，第一次（每次）做的贪心选择一定属于某个最优解）

（第二点我发现可以对照‘割性质’：割上的最小边一定属于某一棵最小生成树，不一定所有最小生成树都有，但是一定有某一棵有）

如何证明贪心算法可成立？

kruskal最小生成树

概念：Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法基于贪心思想，基本思想是从小到大加入边。

主要思想

1. 将图的边按权值大小从小到大依次选取
2. 选取权值最小的边 edge，假设构成该边的两个点为 (point1, point2)，如果 point1 和 point2 已在一个连通图中，则舍弃该边；否则将该边加入最小生成树中
3. 重复步骤 2，直到构成最小生成树为止

证明：

取现有的边$a1,a2,a3....an$，将它们不妨按照从小到大排序。

接下来，当下标$i = 2$时，此时自然可以形成最小生成树

当$n = k$时，假设可以构成最小生成树。

当$n = k+1$时，令图$G$的最小权重边$e = \{i,j\}$连接，剩下的图为$G'$，图$G'$根据归纳假设，由算法可推出：存在$G'$的最小生成树$T'$。令$T = T'\cup \{e\}$，由引理1，$T$是关于图$G$的最小生成树。$Q.E.D$.

$引理1（割性质）：割上的最小边一定属于某一棵最小生成树$

证明：我们假设割$e$不属于任意一棵最小生成树，那么最小生成树中一定有某一个跨越$(S,V/S)$的割$f$，那么最小生成树的图满足$W(f) < W(e)$，那么由于树的性质1得到我们将$f$换成$e$仍然为树，然而其中的某一条边变成了更小的$e$，这说明$W(f) > W(e)$，所以矛盾，$Q.E.D$。

做题感悟

刚刚AC第二场积分赛的重返未来1999那道题，全场当时就我一个人没有AC（捂脸）。

做完之后就感觉自己是纯唐，我感觉就是跟着题意正常地一步一步翻译，并没有特别的小巧思，然而没有做出来肯定是有原因的，在这方面我真的觉得：

我在用：

数值增长直觉
去近似
一个被不等式严格约束的系统

这种题如果不完全照着数学约束写，很容易“差 1 就全错”。 所以即使我

• 思想是对的
• 增长模型是对的

但实现中：

• 上界 +1 写成 +2（包括我的下标管理出现0-base与1-base混淆）
• 没有截断
• 目标状态错
• 开始补丁

这四个叠加，就让代码整体失控了。