贪心算法

做出在当前看来是最好的选择：贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。

1、贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到 –> 必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、满足：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质 -> 迭代

贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关）

1、从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

2、当达到算法中的某一步不能再继续前进时，算法停止。

从问题的某一初始解出发
while (能朝给定总目标前进一步){
	利用可行的决策，求出可行解的一个解元素；
}
return 由所有解元素组合成问题的一个可行解；

【贪心算法存在的问题】

1、背包

最大容量是50KG，装入不同价值的不同液体，问什么样的方案才能使得背包里装的液体的总价值最大？

策略：每一阶段做决策都找出当前条件下的最优解

2、找零钱的问题

输入找零的钱，输出找钱方案中最少张数的方案，比如123元，最少是1张100的，1张20的，3张1元的，一共5张！

策略：每次选择最大的钱，如果最后超过了，再选择次大的面值