什么问题适合贪心法？_什么情况可以使用贪心算法

1.贪心和动态规划:
①贪心: 根据当前状态，作出局部最优的选择 $\rightarrow$ 解决作出选择后产生的子问题。（问题规模：大$\rightarrow$小）

②动态规划: 根据子问题的解,结合当前问题 $\rightarrow$ 作出选择。（问题规模：小$\rightarrow$大）

  
2.性质
①贪心选择性质：所求问题的整体最优解可以由一系列的局部最优选择达到。
②最优子结构性质：一个问题的最优解包含其子问题的最优解。

3.如何证明一个问题可以用贪心法解决
从三个方面：
①贪心选择性质

考察一个问题的整体最优解 $\rightarrow$证明：可修改这个解，使其以贪心选择开始
②最优子结构性质

在规模为n的最优解下，包含的规模为n-1的解是这个规模下的最优解。

③每一步使用贪心选择，可以获得最优的解

 归纳法证明：通过每一步的贪心，最终得到最优解。

 

4.举例：

活动安排问题是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一-公共资源的活动。贪心算法提供了一个简单、漂亮的方法，使尽可能多的活动能兼容地使用公共资源。
设有n个活动的集合E={1,2, …… n},其中每个活动都要求使用同一资源， 如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有要求使用该资源的起始时间 si ;和结束时间 fi ,如果选择了活动 i ,则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动 i 与活动 j 是相容的。也就是说，当 sj≥fi 或si≥fj时，活动 i 与活动 j 相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

分析：

通过分析题目，我们直观上可以看出，在相容的所有活动中选择结束时间较早的会更靠近最优解。

证明：(先将原集合中的活动按照结束时间升序排序，并编号1……n)

 

①贪心选择性质

假设{1……n}个活动有某一最优解的集合E,（集合内的活动按照结束时间升序排序），集合中的第一个活动序号为k。

k=1即结束时间最早的活动先开始，是贪心选择开始的一个最优解

k>1，有结束时间fk>f1，令E' = E - {k}∪{1}，因为k和E中的其他元素是相容的，那么1和E中的其他元素也是相容的。所以，E'也是原问题的一个可行解，而E和E'的活动个数相同，因此E'是原问题的一个最优解。

 

②最优子结构性质

E是原问题的一个最优解，第一个活动为k, 与k相容的所有活动的集合是Sk,。

E'=E-{k} 是原问题产生的一个子问题的解。它是Sk集合下的最优解吗？

假设：最优解E''中活动个数 > E'活动个数 $\rightarrow$ n(E'') +1 >n(E')+1 $\rightarrow$ E不是原问题的最优解！$\rightarrow$ 结论与假设矛盾，假设不成立。

 

③每一步贪心，可以得到最优解。（假设归纳）

最优的方案活动个数为k,设与安排的第前 $i-1$ 个活动相容 $\left (S_{l_{i}}\geq f_{l_{i-1}} \right )$，结束最早的活动的编号为 $l_{i}$ ,那么要证明：$E=\cup_{i=1}^{k} \left \{ l_{i} \right \}$

Ⅰ.k=1时由①知成立

Ⅱ.假设k=x-1时成立，当k=x时,由②最优子结构性质：$E=\cup_{i=2}^{k} \left \{ l_{i} \right \}+\left \{ l_{1} \right \}=\cup_{i=1}^{k} \left \{ l_{i} \right \}$

得证。