贪心算法
选择目前最优策略，不考虑全局最优
三步走
第一步
明确最优解
第二步
明确子问题的最优解
第三步
分别求出子问题的最优解再堆叠出全局最优解
例子
背包问题
有一个背包，最多能承载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.没有太大必要一定要求出全局最优解，“比较优即可”
二、如何分解为子问题
按串行任务分
时间串行的任务，按子任务来分解，即每一步都是在前一步的基础上再选择当前的最优解。
按规模递减分
规模较大的复杂问题，可以借助递归思想，分解成一个规模小一点点的问题，循环解决，当最后一步的求解完成后就得到了所谓的“全局最优解”。
按并行任务分
这种问题的任务不分先后，可能是并行的，可以分别求解后，再按一定的规则（比如某种配比公式）将其组合后得到最终解。
三、如何判段贪心算法的结果逼近了全局最优值
逻辑分析上不会超过忍受范围即可
