贪心法的基本思路：
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
- 不能保证求得的最后解是最佳的；
- 不能用来求最大或最小解问题；
- 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
通俗的例子：
比如中国的货币，只看元，有1元2元5元10元20、50、100
如果我要16元，可以拿16个1元，8个2元，但是怎么最少呢？
如果用贪心算，就是我每一次拿那张可能拿的最大的。
比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿个5元，剩下1元
也就是3张 10、5、1。
每次拿能拿的最大的，就是贪心。
但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数
贪心只能得到一个比较好的解，而且贪心算法很好想得到。
再注意，为什么我们的钱可以用贪心呢？因为我们国家的钱的大小设计，正好可以使得贪心算法算出来的是最优解（一般是个国家的钱币都应该这么设计）。如果设计成别的样子情况就不同了
比如某国的钱币分为 1元3元4元
如果要拿6元钱 怎么拿？贪心的话 先拿4 再拿两个1 一共3张钱
实际最优呢？ 两张3元就够了
贪心就是找距离目标最近的拿，不管最终的结果，只注重局部或者眼前的结果的方法
按照这种方法就是有可能丧失全局最优的
就好比两个人分5个大饼，一次可以拿一个或者两个，不吃完不允许再拿
A：用贪心方法：第一次拿两个，B拿一个，那么B最终拿3个
这个就是贪心方法失败的一个例子
有的时候贪心算法也是可以得到最优解的,比如还是大饼的例子，但是现在总数是7个了
A继续贪心，先两个，再两个就是4个了；
而B先1个，后2个，就只能是3个
网友评论