一看就懂的贪心算法_贪心算法在什么问题上不会有最优解

如何理解贪心算法

我们先看一个例子

假设有一个可以容纳100kg物品的背包，背包可以装各种物品，我们有以下五种豆子，每种豆子的重量和总价值各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又应该装多少？

我们可以这样想，我们只需要计算出每种豆子的单价，按照价格由高到低依次来装豆子，先按单价最高的豆子装，装不满的话，再装价格相对较低的豆子，直到装满为止。

这个问题的解决思路就是用了贪心算法的思想，我们先来看以下贪心算法解决问题的步骤：

第一步：套用贪心算法的问题模型：针对一组数据，事先定义了限制值和期望值，希望从中选择几个数据，在满足限制的情况下，期望值最大。针对刚才的例子，限制值就是装载背包中的豆子不能超过100kg，期望值就是装在背包中的豆子的总价值。这组数据就是5种豆子，从中选出 一部分豆子，满足重量不超过100kg，并且总价值最大。

第二步：尝试用贪心算法来解决：每次选择对限制值同等贡献量的情况下，对期望值贡献最大的数据。针对刚才的例子，每次都从剩下的豆子里选择单价最高的，也就是重量相同的情况下，对价值贡献最大的豆子。

第三步：举例验证算法是否正确：在大部分情况下，举几个例子验证以下短发是否能得到最优解就可以了。

实际上，用贪心算法解决问题，并不能给出最优解。

再来看一个例子，在一个有权图中找一条从顶点S到顶点T的最短路径（路径中边的权值最小）。贪心算法的解决思路：每次都选择一条与当前顶点相连的权值最小的边，也就是对总路径长度贡献最小的边，直到找到顶点T。按照这种思路，我们求出的最短路径是S->A->E->T,路径长度是1+4+4 = 9。

但是，基于这种贪心算法，最终得到的路径并非最短路径，因为路径S->B->D->T更短，长度为6。贪心算法不能解决这个问题的主要原因是在贪心选择过程中前面的选择会影响后面的选择。如果第一步从顶点S到顶点A，那么接下来面对的顶点和边与第一步从顶点S到顶点B是完全不同的。因此，即便我们在第一步选择最优的走法，也有可能因为这一步的选择导致后面的每一步都很糟糕。

贪心算法的应用示例

 如何用贪心算法解决赫夫曼编码

假设有一个包含1000个字符的文件，每个字符占1B(1B = 8bit)，存储这1000个字符需要8000bit，那么有没有更加节省空间的存储方式呢？

假设通过统计分析发现，这1000个字符中只包含六种不同的字符，假设分别是a,b,c,d,e,f。而三个二进制位(bit)就可以表示8个不同的字符，因此为了减少存储空间，每个字符用三个二进制位来表示：a为000，b为001，c为010，d为011，e为100，f为101。那么，存储这1000个字符只需要3000bit，比原来存储方式节省了很多空间。还有没有更加节省空间的方式呢？

此时就需要用到赫夫曼编码了，他是一种非常有效的编码方式，广泛应用于数据压缩中，其压缩率通常为20%-90%。