《算法设计与分析》--贪心算法随笔

1、概述：当一个问题是具有最优子结构性质的时候，我们可以使用动态规划算法求解。但是有时候还是会存在更好的算法的。比如说我们举一个找硬币的例子。如果我们有四种用硬币。它们自制的面值分别是二角五分、一角、五分和一份。现在我们需要找给顾客6角3分钱，我们其实很自然的就会拿出2个二角五分的和1个一角的硬币和3个一分的硬币给顾客。

事实上这种找硬币的方式比较的合理而且是最少的，这里我们首先说一下所用到的算法：首先选出1个面值不超过六角三分的最大硬币，所以取出来的二角五分，所以六角三分减去二角五分，最后剩下了三角八分。再从其中选出不超过三角八分的最大硬币，即又是一个二角五分，这样一直做下去。实际上这就是一个贪心算法的雏形。

其实贪心算法并不会从整体的层面上考虑问题，只是单纯的在局部上面考虑问题的最优解。并且在最终贪心算法得到的问题也是要求是最优的。

找硬币问题本身是具有最优子结构性质的，

最优子结构性质：假设当前决策结果是f[n]，则最优子结构就是要让f[n-k]最优，最优子结构性质就是能让转移到n的状态是最优的，并且与后面的决策没有关系，即让后面的决策安心地使用前面的局部最优解的一种性质。