目录
1、贪心算法
2、贪心算法的证明方式
（1）替换法（反证法）
（2）数学归纳法（递推法）
1、贪心算法
- 定义：对于解决问题的每一个步骤，总选择当前步骤的局部最优解，希望以此达到总体最优。
- 性质：贪心算法与搜索、动态规划一脉相承，但贪心算法并不遍历所有状态空间，也不允许回溯，要求每个步骤必须具有无后效性。
- 故：不是所有问题都能使用贪心算法求解，贪心算法也不一定可以找到整体最优解。贪心算法难点不在于问题求解，而在于对贪心策略正确性的证明。
2、贪心算法的证明方式
（1）替换法（反证法）
- 先依靠贪心算法得出最优解，再证明：将任意步骤的决策替换为任意的其他选择，最后结果都不可能达到更优。
eg：背包负重问题
题目：给定数组 arr 表示 n 个物品各自的重量，背包负重上限为 N，要求在不超过负重上限的情况下，尽可能的多带物品。
解法：贪心算法，每次总拿取最轻物品放入背包
替换法证明：设 利用贪心算法得出的最优解为 [n1, n2, n3, ... , nx] ，现用 m 替换 n1（n1 已是“当前最轻”，故 m > n1），证明能否得到更优解 [m, n2, n3, ... , nx, ny] （比原最优解多放入一个物品 ny）
观察可知： “更优解前 x 项之和“ 必定大于 “原最优解 x 项之和” ，且更优解还多了一项 ny 都没有超限，说明原最优解加上 ny 也必定不会超限，原最优解应为 [n1, n2, n3, ... , nx, ny] 与题设相悖，故反证错误，不存在这样的替换方法。即：替换最优解任意项后，都无法达到更优，得证。
- 替换法实质上是在 尝试证明 “局部最优” 与 “整体最优” 的关联性，若一旦失去局部最优，也必将失去整体最优，则说明贪心策略正确可行。
（2）数学归纳法（递推法）
- 原理：一旦我们证明了在某个起点值时命题成立，且证明出从一个值到下一个值的过程有效（即
n = m 到 n = m + 1），那么任意值都可以通过反复使用这个方法推导出来
- 数学证明步骤：
step1：证明 当 n = 1 时，命题成立
step2：证明 如果在 n = m（m 为任意自然数）时命题成立，那么可以推导出 n = m + 1 时命题也成立
- 在利用数学归纳法证明时，最重要的是选好命题，递推的过程就是步骤执行的过程
eg：背包负重问题
题目：给定数组 arr 表示 n 个物品各自的重量，背包负重上限为 N，要求在不超过负重上限的情况下，尽可能的多带物品。
解法：贪心算法，每次总拿取最轻物品放入背包
选择命题： “每次选择当前最轻的物品，能使背包余留空间更大”
数学归纳法证明：显然
