一、基本概念：
所谓贪心算法是指，在对问题求解时，总是做出在当时看来是最好的挑选。也便是说，不从全体最优上加以考虑，他所做出的仅是在某种意义上的部分最优解。
贪心算法没有固定的算法结构，算法规划的关键是贪心战略的挑选。有必要留意的是，贪心算法不是对一切问题都能得到全体最优解，挑选的贪心战略有必要具有无后效性，即某个状况今后的进程不会影响曾经的状况，只与当时状况有关。
所以对所选用的贪心战略必定要仔细剖析其是否满意无后效性。
二、贪心算法的基本思路：
1.树立数学模型来描绘问题。
2.把求解的问题分红若干个子问题。
3.对每一子问题求解，得到子问题的部分最优解。
4.把子问题的解部分最优解组成本来解问题的一个解。
三、贪心算法适用的问题
贪心战略适用的条件是：部分最优战略能导致发生大局最优解。
实践上，贪心算法适用的状况很少。一般，对一个问题剖析是否适用于贪心算法，能够先挑选该问题下的几个实践数据进行剖析，就可做出判别。
四、贪心算法的完成结构
从问题的某一初始解动身；
while （能朝给定总方针行进一步）
{
运用可行的决议计划，求出可行解的一个解元素；
}
由一切解元素组组成问题的一个可行解；
五、贪心战略的挑选
因为用贪心算法只能通过解部分最优解的战略来到达大局最优解，因而，必定要留意判别问题是否合适选用贪心算法战略，找到的解是否必定是问题的最优解。
六、例题剖析
下面是一个能够试用贪心算法解的标题，贪心解确实不错，惋惜不是最优解。
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品能够分割成恣意巨细。
要求尽可能让装入背包中的物品总价值最大，但不能超越总容量。
物品 A B C D E F G
分量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
剖析：
方针函数： ∑pi最大
约束条件是装入的物品总分量不超越背包容量：∑wi<=M( M=150)
（1）根据贪心的战略，每次挑选价值最大的物品装入背包，得到的成果是否最优？
（2）每次挑选所占分量最小的物品装入是否能得到最优解？
（3）每次选取单位分量价值最大的物品，成为解本题的战略。
值得留意的是，贪心算法并不是彻底不能够运用，贪心战略一旦通过证明建立后，它便是一种高效的算法。
贪心算法仍是很常见的算法之一，这是因为它简单易行，结构贪心战略不是很困难。
惋惜的是，它需求证明后才干真实运用到标题的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解必定由在贪心战略中存在的子问题的最优解得来的。
关于例题中的3种贪心战略，都是无法建立（无法被证明）的，解说如下：
（1）贪心战略：选取价值最大者。反例：
W=30
物品：A B C
分量：28 12 12
价值：30 20 20
根据战略，首要选取物品A，接下来就无法再选取了，但是，选取B、C则更好。
（2）贪心战略：选取分量最小。它的反例与第一种战略的反例差不多。
（3）贪心战略：选取单位分量价值最大的物品。反例：
W=30
物品：A B C
分量：28 20 10
价值：28 20 10
根据战略，三种物品单位分量价值相同，程序无法根据现有战略作出判别，假如挑选A，则答案过错。
