参考网址：贪心算法
参考书籍：《算法导论》

前言：

求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化问题，使用动态规划算法来求最优解有些杀鸡用牛刀了，可以使用更简单、更高效的算法。贪心算法(greedyalgorithm)就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。贪心算法并不保证得到最优解，但对很多问题确实可以求得最优解。
贪心算法只需考虑一个选择（即贪心的选择），在做贪心选择时，子问题之一必是空的，因此，只留下一个非空子问题。基千这些观察，我们将找到一种递归贪心算法来解决活动调度问题，并将递归算法转化为迭代算法，以完成贪心方法的过程。它们说明了贪心算法和动态规划之间 的关系。

可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。

1、贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

3、贪心算法与动态规划算法的差异

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。
但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?这个后面说。

经典例1、活动安排问题：

设有$n$个活动的集合$E=1,2,\dots ,n$，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 $Ei$ 都有一个要求使用该资源的起始时间$si$和一个结束时间$fi$ ,且$si<fi$ 。如果选择了活动i，则它在半开时间区间$[si,fi)$内占用资源。
若区间$[si,fi)$与区间$[sj,fj)$不相交，则称活动i与活动j是相容的。也就是说，当$si>=fj或sj>=fi$时，活动i与活动j相容。
要安排尽量多的活动，获得最大兼容活动集（注意不是最大时间占用！只要求活动数多，举办的活动多，不要求活动室被使用时间最高效率）
待安排的活动开始结束时间如下:

思路：

1.证明最优子结构性质：

假设$Sij$是在$ai$结束之后开始，而且在$aj$开始之前结束的那些活动的集合，假定我们希望求$Sij$的一个最大的相互兼容的活动子集，进一步假定$Aij$就是这样一个子集，$A_{ij}$一定包含至少一个活动$a_k$(如果连一个活动都不能兼容，说明这个集合无解，根本没有兼容集合)。由于最优解包含活动$a_k$,我们得到两个子问题：寻找$Sik$中的兼容活动（在$ak$结束之后开始且$ak$开始之前结束的那些活动）以及寻找$Skj$中的兼容活动（在$ak$结束之后开始且在$aj$开始之前结束的那些活动） 也就是找找那些未被活动$a_k$占用的时间是否还可以兼容活动

所以 A i j = A i k ∪ { a k } ∪ A k j A_{ij}=A_{ik} \cup \{ak\}\cup A_{kj} Aij​=Aik​∪{ak}∪Akj​

例如图中可看出 { 1 , 4 } , { 3 , 2 } , { 3 , 4 } \{1,4\},\{3,2\},\{3,4\} {1,4},{3,2},{3,4}兼容，
如果初始的活动是
$a_k=1$ 可得 A i j = { ∅ } ∪ { 1 } ∪ { 4 } A_{ij}=\{ \emptyset \} \cup \{1\}\cup \{ 4\} Aij​={∅}∪{1}∪{4}
$a_k=3$ 可得 A i j = { ∅ } ∪ { 3 } ∪ { 2 } A_{ij}=\{ \emptyset \} \cup \{3\}\cup \{ 2\} Aij​={∅}∪{3}∪{2}或者 A i j = { ∅ } ∪ { 3 } ∪ { 4 } A_{ij}=\{ \emptyset \} \cup \{3\}\cup \{ 4\} Aij​={∅}∪{3}∪{4}
$a_k=2$ 可得 A i j = { 3 } ∪ { 2 } ∪ { ∅ } A_{ij}=\{ 3 \} \cup \{2\}\cup \{ \empty\} Aij​={3}∪{2}∪{∅}

用$c[i,j]$表示集合$Sij$的最优解的大小，则可得递归式
式$$c[i,j]=c[i,k]+c[k,j]+1$$ 易知 A i j = A i k ∪ { a k } ∪ A k j A_{ij}=A_{ik} \cup \{ak\}\cup A_{kj} Aij​=Aik​∪{ak}∪Akj​的解是最优解，而$A_{ik},A_{kj}$还可以向下分解，且每个部分的解都是最优解，否则可以用反证法:
如果可以找到$S_{kj}$的一个兼容活动子集$A_{kj}^{{}^{\prime }}$，满足$|A_{kj}^{{}^{\prime }}|>|A_{kj}|$,则可以将$A_{kj}^{{}^{\prime }}$而不是$A_{kj}$作为$S_{ij}$的最优解的一部分。这样就构造出一个兼容活动集，其大小$|A_{ik}|+|A_{kj}^{{}^{\prime }}|+1>|A_{ik}|+|A_{kj}|+1$,与$A_{ij}$是最优解的假设矛盾。

证明总结:

一般而言，证明最优子结构，只需要证明细分后的解的和一定是没细分的解的最优解即可，否则一定存在一个更优解，这和最优解的假设相悖，可用反证法说明一定是最优解。

2.贪心选择性质证明：

定理：考虑任意非空子问题$S_k$,令$a_m$是$S_k$中结束时间最早的活动，则$a_m$在$S_k$的某个最大兼容活动子集中。

证明：

假设$A_k$是$S_k$的一个最大兼容活动子集，且$a_j$是$A_k$中结束最早的一个活动，则有两种情况：

• $a_j=a_m$ 则根据上面的假设：$a_j$是$A_k$中结束最早的一个活动，$A_k$是$S_k$的一个最大兼容活动子集，所以$a_m$就在$S_k$的一个最大兼容活动子集中。
• 否则$a_j\ne a_m$（如图）,那么$a_j$是$A_k$中结束最早的一个活动， A k ′ = ( A k − { a j } ) ∪ { a m } A^{'}_k=(A_k-\{a_j\})\cup\{a_m\} Ak′​=(Ak​−{aj​})∪{am​}也就是用$a_m$替换了$a_j$，因为$A_k$是$S_k$的一个最大兼容活动子集，所以所有的活动都不相交。如图可见 { a m , 4 } 和 { a j , 4 } \{a_m,4\}和\{a_j,4\} {am​,4}和{aj​,4}都是最大兼容活动子集。容易知道，$a_m$是全部的活动中结束时间最早的，而$a_j$只是某个最大兼容活动子集中的最早，所以一定有$a_m$的结束时间$f_m>=f_j$,如果他们不相等，那肯定是$a_m$先结束，用$a_m$替换$A_j$里面的$a_j$一定不会引发冲突！
  从而结合以上两点，定理得证。

证明了上述两个性质后，就说明此问题贪心算法可以得到最优解了。
而只需要证明最优子结构，就可以使用动态规划了。所以可以看出，贪心最优解的求解其实是比动态规划更加严格的。
输入：

8
1
12
1 2 1 3 8 4 11 9
2 4 5 7 12 5 12 10

输出：

5
1 2
2 4
4 5
9 10
11 12

输入：

11
0
14
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14

输出：

4
1 4
5 7
8 11
12 14

代码实现：

# 活动安排的贪心算法
# 输入：活动数量，开始时间，结束时间,活动开始时间，活动结束时间
activity_num=int(input())
start_time=int(input())
end_time=int(input())
activity_s=input().split()
activity_e=input().split()

activity=[]
max_activity=[]
start=start_time
end=end_time

for i in range(0,activity_num):
    activity.append({'start':int(activity_s[i]),'end':int(activity_e[i])})

activity.sort(key=lambda info: info['end']) # 对结束时间排个序
for i in range(0,activity_num):
    if activity[i]['start']>=start and activity[i]['end']<=end:
        max_activity.append(activity[i])
        start=activity[i]['end']
print(len(max_activity))
for act in max_activity:
    print(act['start'],act['end'])

可以看到贪心选择的复杂度仅仅为排序$O(NlogN)$比起穷举的指数级的复杂度，已经大大降低了计算次数。
而动态规划算法时间复杂度$O(N^3)$，堪称杀鸡焉用牛刀的典范
参考网址:算法导论 16.1-1活动选择问题的动态规划算法
动态规划后面看，相应的代码我后面再放在动态规划的博客里。

例2、0-1背包问题和背包问题：

0-1背包问题:
给定$n$种物品和一个背包。物品$i$的重量是$Wi$，其价值为$Vi$，背包的容量为$C$。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
在选择装入背包的物品时，对每种物品$i$只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品$i$。

背包问题：
与0-1背包问题类似，所不同的是在选择物品$i$装入背包时，可以选择物品$i$的一部分，而不一定要全部装入背包，$1<=i<=n$。

0-1背包问题不能用贪心解决,
但是背包问题可以。
用贪心算法解背包问题的基本步骤：
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
（待续）

1.证明最优子结构：​

2.证明贪心选择性：