贪心算法

选择目前最优策略，不考虑全局最优

三步走

第一步

明确最优解

第二步

明确子问题的最优解

第三步

分别求出子问题的最优解再堆叠出全局最优解

例子

背包问题
有一个背包，最多能承载150斤的重量，现在有7个物品，重量分别为[35, 30, 60, 50, 40, 10, 25]，它们的价值分别为[10, 40, 30, 50, 35, 40, 30]，如何使背包背走最多价值的物品

方法一：

1.在重量限制范围内，价值最大的选择是最优解
2.每次尽量选择当前价值最高的物品，称为“局部最优解”
3.选择4 2 6 5；总重量130；总价值165；

方法二

1.质量最轻为最优解
2.选择6 7 2 1 5；总重量：140；总价值：155；
方法一比较好

核心问题

一、为何求局部最优解
1.原问题复杂度过高
2.求全局最优解的数学模型难以建立；
3.求全局最优解的计算量过大
4.没有太大必要一定要求出全局最优解，“比较优即可”
二、如何分解为子问题

按串行任务分
时间串行的任务，按子任务来分解，即每一步都是在前一步的基础上再选择当前的最优解。

按规模递减分
规模较大的复杂问题，可以借助递归思想，分解成一个规模小一点点的问题，循环解决，当最后一步的求解完成后就得到了所谓的“全局最优解”。

按并行任务分
这种问题的任务不分先后，可能是并行的，可以分别求解后，再按一定的规则（比如某种配比公式）将其组合后得到最终解。

三、如何判段贪心算法的结果逼近了全局最优值

逻辑分析上不会超过忍受范围即可