贪心算法详解

三步思路

1. 明确到底什么是最优解
2. 明确什么是子问题的最优解
3. 分别求出子问题最优解再堆叠出全局最优解

基本概念

所谓贪心算法，在对问题求解时，总是做出在当前看来是最好的选择，即不从整体最优上加以考虑，所做的仅仅是在某种意义上的局部最优解。 贪心算法没有固定的框架，算法设计的关键是贪心策略的选择，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关）。

基本思路

• 建立数学模型来描述问题
• 对求解的问题分成若干个子问题
• 把每个子问题求解，得到子问题的局部最优解
• 把子问题的局部最优解合成原来问题的一个解

存在的问题

• 不能保证求得的最后解是最佳的
• 不能用来求最大值或最小值问题
• 只能求满足某些约束条件的可行解的范围

适用的问题

前提：局部最优策略能导致产生全局最优解

贪心选择性质

所求问题的整体最优解可以通过一系列局部最优的选择，即，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。贪心算法以迭代的方式做出相继的贪心选择，没做一次贪心选择就将所求问题简化为规模更小的子问题，对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。

实现框架

从问题的某一初始解出发：

while(朝给定总目标前进一步){
  利用可行的决策，求出可行解的一个解元素
}

由所有解元素组合成问题的一个可行解;

例题分析

eg：有一个背包容量 m=150，有7个物品，物品可以分割成任意大小，要求尽可能让背包中的物品总价值最大，但不能超过总容量。

• 物品：A B C D E F G
• 重量：35 30 60 50 40 10 25
• 价值：10 40 30 50 35 40 30

分析：目标函数： ∑pi 最大

约束条件是装入的物品总质量不超过背包容量 ∑wi<=M( M=150)

1. 根据贪心策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ ×
2. 每次挑选所占重量最小的物品装入是否能得到最优解？ ×
3. 每次选取单位重量价值最大的物品 ×