贪心法的证明（学习笔记）
不要相信玄学，要相信科学。----yxc
数学思路
设贪心法得解为res，最优解为ans，求证res==ans
数学上证明A=B可以用证明A>=B A<=B的方法
注意:这里我们以求最小值一类的为例
求证ans<=res
由“最优解”的定义得:ans是合法方案中的最小值
我们知道贪心解法得到的一定是合法解，所以res是合法方案之一
∴ans<=res
求证ans>=res(或者说ans!<res)
我们可以使用“调整法”
我们先假设ans<res,那么它们的方案一定存在不同之处
那么我们先找到第一处不同
我们试着将最优解法中的决策修改为贪心解法的决策方法
证明出我们修改方案的过程中没有改变ans
最终我们一步步地将最优解法等价变换为贪心解法，且没有改变ans
那么ans没有小于res的可能
∴ans>=res
∴ans==res
建议搭配Acwing.1010等题目食用以辅助理解
