1. 贪心算法定义[1]
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。
2. 算法思路[2]
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。
3. 算法特性[3]
贪心算法可解决的问题通常大部分都有如下的特性：
1、有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。
2、随着算法的进行，将积累起其他两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
3、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
4、还有一个函数检查是否一个候选对象的集合是可行的，即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
5、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
6、最后，目标函数给出解的值。
4. 使用条件[4]
利用贪心法求解的问题应具备如下2个特征。
1、贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。
5. 解题策略 [5]
贪心算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优选择。使用贪心策略要注意局部最优与全局最优的关系，选择当前的局部最优并不一定能推导出问题的全局最优。贪心策略解题需要解决以下两个问题：
1、该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质；
2、制定贪心策略，以达到问题的最优解或较优解 。
要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。
6. 存在问题 [6]
贪心算法也存在如下问题：
1、不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑 ；
2、贪心算法一般用来解决求最大或最小解；
3、贪心算法只能确定某些问题的可行性范围。
7. 应用实例
1. 问题描述
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
2. 问题分析
我下面所说的子段：被绳子被剪成的每一段都称为子段。
不可再减子段：无论怎么剪，该子段的子段长度乘积都无法达到绳子本身的长度。
由题可知绳子的长度最小为2，当绳子的长度为2时，只有一种剪法（1和1）乘积为1，当绳子的长度为3时，也只有一种剪法（1和2）乘积为2，当绳子的长度为4时，有两种剪法（1和3、2和2）且最大乘积为4，当绳子的长度为5时，有两种剪法（1和4、2和3）且最大乘积为6...
由此递推可以看出当绳子的长度为2或3时，无论怎么剪，子段的乘积都无法达到绳子本身的长度，而当绳子的长度不断增加，总有一种剪法可以使子段长度乘积等于或超过本身长度，所以2和3为不可再剪子段，其中3为最大不可再剪子段。用贪婪算法解此题的思路就是“尽可能的把绳子剪为最大不可再剪子段的长度，并且满足所有子段长度都为不可再剪子段”。简单来说，就是只能把绳子剪成2或者3的小段，并且3越多越好。
3. 代码实现
#include <iostream>
#include <iostream>
#include <cmath>
using namespace std;
int maxProductOfCuttingRope(int length) {
if(length < 2)//不满足n>1
return 0;
if(length == 2)//长度为2时,结果为1
return 1;
if(length == 3)//长度为3时,结果为2
return 2;
//计算最多能剪出多少个长度为3的子段,个数记为divideBy3
int divideBy3 = length / 3;
//剪完之后最后剩下的绳子长度有0，1，2三种情况
if(length - divideBy3 * 3 == 1)//如果剪完3最后只剩一个1
divideBy3 -= 1;//就要留下一个3凑成四，然后可以剪成两个2
//那么现在剩下长度就0，2，4三种情况
int divideBy2 = (length - divideBy3 * 3) / 2; //计算一下能剪出几个长度为2的子段，个数记为divideBy2
//最后得出的最优解最优解即为 3的divideBy3次幂乘2的divideBy2次幂
return (int) (pow(3, divideBy3)) * (int) (pow(2, divideBy2));
}
int main(){
cout<<maxProductOfCuttingRope(8)<<endl;
return 0;
}
感谢阅读，如有问题欢迎指正！
[1][2][3][4][5][6] 引用自百度百科
