贪心算法的基础知识

1.个人理解：是一种逐步逐步（不回溯）求取最符合条件的方法。（每一步都取出一个相对于其它元素最符合条件的元素）。 所谓“贪心”是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，所以叫贪心算法。 贪心选择性质：指所求问题的最优解可以通过一系列局部最优解来达到。

2.贪心算法的漏洞：a. 不能保证求得的最后解是最佳的； b. 不能用来求最大或最小解问题； c. 只能求满足某些约束条件的可行解的范围。

a. 有序列表 eg1:在一堆草莓中，你有五次选择的机会，每次选一颗，你第一次选择，贪心的选择了所有草莓中最大的并拿走了；第 二次选择，又贪心的选择了剩下的最大的；第三次、第四次都是这样，直到选完五次。这就是贪心。

eg2:实用：在一堆宝藏里面，每个宝物的价值相同，而重量不同，然而你只有一条船只能携带500斤的宝物

我相信贪心的人肯定会选择最轻的宝物装上船，来保证数量多。 假如总共有11件宝物，s[]中的元素代表11件宝物的重量，court代表贪心的选择了几件宝物。

从上面的例子可知我们先要对宝物的重量进行排序，已经排完从小到大，自然就好挑选了嘛。

有兴趣深入的可以看下贪心算法之背包问题。