贪心算法局限性

贪心算法局限性

贪心算法可以用来解决优化问题，与其他算法相比，贪心算法的最大优点是在大多数情况下易于实现且非常高效，但也存在一些问题。

贪心算法不能对所有问题都保证解是最佳的，因为它总是从局部出发，并没从整体考虑。在不满足贪心选择性质时，局部最优解可能无法合成为整体最优解，也不一定接近最优解。0-1背包问题和旅行商问题是贪心算法无法保证产生最佳解决方案的问题示例。

当需要实时解决方案且近似答案足够好时，贪心算法可能适用。如果问题满足贪心选择和最优子结构性质，贪心算法可以得到最优解；否则需要评估近似答案的质量，不能保证最优。

硬币找零

假设有1元、5元、11元这三种面值的硬币，给定一个找零金额，比如28元，最少使用的硬币组合是什么？

使用贪心算法可以得到结果为[11, 11, 5, 1]，总共是4个硬币。对于这个例子而言，4个硬币的确是最优解。但是假如找零是15元呢？使用贪心算法结果为[11, 1, 1, 1, 1]，共用了5个硬币，然而最优解是[5, 5, 5]，共3个硬币。硬币找零问题可以使用动态规划计算出最优解。

0-1背包

部分背包问题可以用贪心算法实现，是因为选择放入的物品可以进行拆分，即并不需要放入整个物品。与之对应的另一种背包问题为0-1背包问题，这个时候整个物品不可以拆分，只可以选择放入或者不放入。0-1背包问题用贪心算法并不能求得准确的解，需要用动态规划算法求解。

假设0-1背包的容量为8，物品的重量和价值分别为：

使用贪心算法会优先选择单位重量价值最高的物品，当拿完物品1和物品2后，背包剩余容量为8 - 2 - 3 = 3。由于物品不可拆分，背包无法装入物品3和物品4。最终总价值为3 + 4 = 7。

但是使用动态规划可以计算出最佳方案是选择物品2和物品4，最大价值为4 + 6 = 10。