贪心思想

什么是贪心思想

根据度娘的介绍，我们可以看出贪心算法是一个比较契合人类思维的算法，他就是每次都选取当下最好的情况，所以得到的未必是最优解，但是一定是局部最优解，一个非常接近最优解的情况。

贪心思想的特点

1. 不回溯：选定一个分量后，就不重试其他可能了，这也是为什么回溯法最终得到的是全局最优解而贪心只能得到局部最优解的原因。
2. 使用局部优化策略即贪婪策略的主要原因不是得到全局最优解，而是尽量使用较小的计算开销得到一个较为贴近最优解的优化解，因此极有可能得到的就是一个近似解。
3. 不同的贪心策略会得到不同的贪心近似解，但是大致上都是在精确最优解附近摆动。
4. 常常使用的是使目标函数有最大收益的策略就是贪心策略，即局部性概念。

典型例题精讲

找零钱问题

假设有4种硬币，他的面值分别是二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。

正常思维:我们会不假思索地拿出2个二角五分的硬币,1个一角的硬币和3个一分的硬币交给顾客。

这种找硬币方法与其他的找法相比，所拿出的硬币个数是最少的。这里，我们下意识地使用了这样的找硬币算法： 首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一 个二角五分，如此一直做下去。即每次都选择尽可能大的硬币进行拼凑，这种找硬币的算法实际上就是贪心算法，只是巧合的是，这里的贪心近似解与全局最优解刚好相同。

总结：所以贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法并不从整体最优 上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。

活动安排问题

设有n个活动的集合E={1,2,…,n}，每个活动都有相对应的占用舞台的起始时间和结束时间，并且只有一个舞台可以使用，而且保证一个活动开始时必须一直进行到结束，即不能中途切换活动。我们要寻找到一个最好的策略使得尽可能多的活动使用这个舞台。

首先，由于活动不能中途切换，且后面的活动必须等到前面的活动结束才能开始，所以每个活动之间肯定是相容的，即任意两个活动的占用舞台的时间区间不相交。这里我们保证输入的活动是以其完成时间的非递减顺序排列的，所以按照贪心策略，我们只需要每次都选择最早完成时间的相容活动加入活动集合中即可，这种方法每次都选择相容活动并且由于每次选取的都是最早完成的活动，直观上来看，也就为后面的活动留下了更过的时间，所以可以将时间段极大化，应该能够得到一个较为接近全局最优解组合的答案。并且由于我们只需要每次选取最早完成的活动即可，所以只需遍历一遍活动数组即可，时间复杂度仅仅为O(n)，空间复杂度没有借用队列，堆栈等辅助数据结构题，所以空间复杂度也只是一个一维n数组，空间复杂度也仅仅为O(n)，那么总体来看，我们只是用了很小的时间和空间复杂度就得到了一个非常接近全局最优解的组合，可见其开销之小，因此这种方法非常适用于实际生活中。即使输入的活动完成时间是混乱排序的，那么只需要使用快排或者堆排序，归并排序进行重排列即可，时间开销也只是提升到了O(nlogn)。伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static int greedySelector(int [] s,int [] f,boolean a[]){
    //记录数组边界值
    int n=s.length()-1;
    //用来记录a[i]活动是否选择进行，第一个活动肯定是要进行的
    a[1]=true;
    int j=1;
    //选择的活动数量，因为已知第一个活动进行，所以初始化为1
    int count=1;
    for(int i=2;i<=n;i++){
        //对活动i进行检验看是否是最早的当前完成时间
        //s[i]代表活动i的开始时间
        //f[j]代表活动j的结束时间
        if(s[i]>=f[j]){
            a[i]=true;
            j=i;
            count++;
        }
        else{
            //不选择此活动
            a[i]=false
        }
    }
    return count;
}

机器调度问题

现在有n个任务和足够多台的机器，假定任何时间一台机器只能执行一个任务，设任务i的开始时间为si,完成时间为fi,那么si<fi,[si,fi]代表任务i的作业时间区间，成两个任务i,j重叠是指两个任务的时间区间有重叠，例如：区间[1,4]和区间[2,5]，而[1,4]和[4,7]没有重叠。可行的任务分配是指分配中没有将重叠的任务分配给同一台机器。最优分配是指占用机器数最少的可行分配。例如：

按照贪心策略：那么每次我们都将遇到重叠任务时加一台机器，且每次都尽可能将任务放到所有空闲机器中完成时间最小的机器上。如下图：

这里一共有7和任务，我们按照贪心策略，每次都尽量使用旧机器，实在迫不得已了在开新机器，然后每台用过的机器的可用时间为这台机器上最近执行任务的完成时间。如果一个新任务的起始时间>=这些机器的最小可用时间，则安排在这个旧机器上，否则就只能使用新机器了，如上图，M2是在M1在执行a，而f无法执行时开始使用的，M3是在执行c却发现M1,M2都繁忙时使用的，d其实用M2,M3均可以，这里因为每次都尽可能保证三台机器平均使用寿命相同，每次都选择空闲时间更长的机器。这里的任务并不是按照开始时间非递减顺序排列的，所以我们首先可以使用Min-堆存放每台机器的可用时间即进行堆排序重排列，这样每次取出的新任务一定是当前开始时间最早的，所以时间复杂度为O(nlogn)。

我们发现虽然理论上贪心算法一般不能得到全局最优组合，但是对于这种机器调度或者找零钱等问题，一般使用贪心算法却总是能够直接得到整体最优解。所以贪心算法也并不是一定相对整体最优解有偏差。

最短路径

给定一个有向图G，一个源节点s，目的节点d,找到一条从s到d的对短路径。这里如果不是用回溯法或者分枝-限界法，一般最终求得的都不是整体最短路径，而只是一个相对最短路径，但是相对的时间开销也会小很多。如果利用贪婪算法，那么每次我们离s点最近的下一个节点q，然后在选择离q最近的且不再前面选择过的节点t，直至到达d，这种策略即为最短路径贪婪策略。

例如下面这道例题，我们寻找从1到5的最短路径：

按照贪婪策略应该为1->3->4->2->5，路径长度为2+2+1+5=10,但是对于1->4->5只需要6就可以到达，所以按照贪心法找大的一般都不是整体最短路径，而只是一个优化组合。

装载集装箱问题

尽可能在有限的承重量情况下多装入集装箱。这里我们所采用的贪心策略就是尽可能选择装入小（从小到大排序装入）的集装箱直至装到不能再装入集装箱。对于混乱排列的集装箱使用快排即可。我们发现其实这里得到的贪心解就是最优解。证明如下：

首先一定是替换集装箱，而不是加入集装箱。因为此时已经不能装入更多的箱子里，并且因为是从小到大装入的，所以肯定是不足以装入下一个箱子了，所以唯一的一种情况就是取除前面已经装入的某个箱子后+剩余的不足以装入更大箱子空间后可以装入后面更大的箱子了，但是总体来看，箱子数没有发生变化，只是剩余空间变小了，空间利用率变大了。

所以有关数量不涉及到空间利用率或者效益值的问题，一般贪心得到的就是最优解。

0/1背包问题

与上面不同的是，这里就涉及到了效益值的问题，题意如下：设有容量c的背包和n件物品,物品i的重量为wi ;假定装入物品i获得的效益值pi,试给出一装入物品的方法,使获得的总效益值最大。

第一种贪心策略：

对于这种问题，我们第一个想法就是尽可能装入更多的物品，那么效益值应该也会尽可能的大，所以才用的是每次都装入小的物品，直至不能装入物品了。这种策略并不一定会得到最优解。对于质量小的物品效益值特别低，质量略大的物体效益值特别大的情况就有一点捡了芝麻丢了西瓜的意思，如下：n是物品数量，c是背包容量，p是效益值

n=3,c=105,p=[100,10,10]，我们按照上面的贪心策略最终得到的贪心解为[1,0,0]效益值为20，但是最优解却是[0,1,1]效益值为30，所以需要改变策略。

第二种贪心策略：

那么还有一种就是每次尽可能选大的效益值物品拿，这样整体效益值也会尽可能的大，所以每次都是效益值最大的物品，直至不能装入物品了。这种策略其实也不一定能够得到最优解。对于效益大的物品质量特别大，而效益值略小的物品质量却特别小的情况就有些欠妥，如下：

n=3,c=25,w=[10,15,20],p=[80,99,100]，此时按照上面的贪婪策略最终得到的贪心解为[0,0,1]效益值为100，但是最优解却为[1,1,0]效益值为179。所以综合来看上面两种贪心策略都不是太好，他们距离最优解都有较大的差距，所以需要采用一种折中的方法如下：

第三种贪心策略：

我们每次不是选择质量小或者效益值大的物品装入，而是引入一种新的概念效益密度值，他的计算公式为m=p/w,表示单位质量的某种物体所含有的效益值，这样我们每次都选取效益密度值更大的物体，对于整体视角来看，每次选取的都是相对来说效益值较大的物体。这样却是可以缩小贪心解和最优解之间的误差，但是也会存在特殊情况，因为某种物品的效益值=该物品效益密度值*物体总质量，那么对于效益密度值很大，但是其物体质量太小，最终产生的效益值微乎其微不能对总体带来太大影响反而占用了部分空间从而造成了较大的背包碎片没办法放入大质量物体也会导致误差较大，例如：

n=3c=30,w=[20,15,15],p=[40,25,25],我们按照上面的策略进行选取，首先需要计算出效益密度值并按照密度值递减顺序进行重排序，最后贪心解为[1,0,0]效益值为40，优化解为[0,1,1]效益值为50，之所以会产生这种偏差，就是因为选取了物品1以后产生了较大的背包剩余空间，而无法放入2,3，仅仅物品1产生的效益值又不是太大导致的。但是综合考虑，三种贪心策略中第三种贪心策略发生特例的情况概率较小，且一般产生的误差不是太过于离谱，所以对于一般的0/1背包问题，我们选择效益密度方法进行贪婪选取。

伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void Selector(int [] w,int []p,int c){
    //一定要记住首先需要转换类型
    //因为密度值一般只有在小数部分才能比出大小
    //两个整型相处得整型
    int->double
    //计算效益密度值
    double m[];
    for(int i=0;i<w.length();i++){
        m[i]=p[i]/c[i]
    }
    //快排按照密度值重排列
    //贪婪选取
    for(int i=0;i<w.length();i++){
        if(物品i可以装入背包){
            //装入物品i，此时i应该是效益密度值最大的物品
        }
        else{
            //舍弃物品i
            continue;
        }
    }
}

算法时间复杂度为O(nlogn)，因为贪心法往往不能得到精确解，所以定义贪心解和最优解的误差用一下比值的百分比来度量：

$$误差=|优化值-贪心解值|/优化值*100\%$$

对于上面的三种策略一般误差不会超过100%，但是当出现某个物品的质量和密度值非常大远超其他物品的时候，误差往往超过100%，即贪心解几乎是优化解的n倍😂！

思考：能否进一步优化保证误差小于30%?

实际上是可以做到的，这里介绍一种k-优化算法，他可以保证贪心解与最优解的误差非常之小，但是相对来说也更复杂，但是对比回溯法和分枝-限界法时间开销和空间开销又较小。其改良后的误差范围为

$$误差=1/(k+1)*100\%$$

所以一般对于这种方法k=2误差就已经非常小了。那么这种算法思路入下：

• 首先k-优化算法也需要对物品进行效益密度值从大到小重排列
• 先将一些物品按照分类讨论的方法装入背包，然后剩下的物品在进行贪心法选取
• 预先装入的物品（即分类讨论装入的物品）数量不能超过k
• 对所有物品数不超过k的物品子集都执行上面的过程，并从多个效益值解中选取最好的解作为k-优化算法的优化解

例如：n=4,w=[2,4,6,7],p=[6,10,12,13],c=11。我们这里使用2-优化算法，理论上误差值应该控制在了33%以内。最后我们将证明误差是否在33%以内，其步骤如下：

首先当k=0时，即有0件物品事先装入背包，剩下的物品按照贪心策略选取，实际上不就是直接按照效益密度值贪心策略选取嘛😄，最终贪心解为[1,1,0,0]效益值为16。

当k=1时即说明有一件物体可以不用按照贪心策略方法选取而是直接事先装入背包，此时有{1},{2},{3},{4}四个子集情况，对于事先放入{1}和{2}实际上与k=0产生的结果相同，因为他们两个是效益密度值较大的前两位，对于此时k=1时最终的选取结果都是[1,1,0,0]和k=0时无差异。而当事先放入物品3，然后剩下的物品进行贪婪策略选取时，最终的解是[1,0,1,0]效益值为18，当事先放入物品4时，产生的解则为[1,0,0,1]效益值为19。因此此时已经发现产生更好的优化解了，为[1,0,0,1]。

当k=2时，考虑的情况有{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}。因为{3,4}已经超出范围了所以直接排除，剩下的解分别为[1,1,0,0],[1,0,0,1],[0,1,1,0],[0,1,0,1]最终发现最后一种情况即{2,4}会产生更好的效益值为23，因此k=2时最终的优化解为[0,1,0,1]，效益值为23。

综合上面三个解，最终的优化解就是[0,1,0,1]，效益值为23并且经过检验发现此时的组合就是最优解的答案，误差为0，确实在33%以内，而对于k=1是产生的误差为(23-19)/23*100%=17.4%在理论值50%以内。因此k-优化算法确实做到了事先要求的解，他相较于效益密度值贪婪策略更为优秀。

思考：既然如此为什么还要用回溯法和分枝-限界法？

你一定会有上面这种疑惑，既然k-优化算法已经如此优秀了，只要每次都使用2-优化甚至3-优化算法就已经可以得到误差非常小的贪心解了，在使用回溯法和分枝-限界法不是多此一举吗？实际上这种k-优化算法使用次数非常少，其根本原因是违背了算法的本质目的，算法是尽可能找到一个内在规律然后进行推算选中最优解，而k-优化算法确实在对特殊情况进行枚举分类讨论，对于小问题还好，对于数量级非常大的问题，其方法就非常复杂了，远不如回溯和分枝-限界法的扩展状态空间树方便，并且归根结底k-优化算法还是会产生误差的，对于精确计算，回溯法和分枝-限界法还是更加可信。

构造哈夫曼编码

概念：什么是哈夫曼编码？

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。定长变码需要300,000位，而按表中变长编码方案，文件的总码长为：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000。

这样使用更频繁的字符如a变长码长度更短仅仅为1个位，比用定长码的情况总码长度少了约45%。

思考：哈夫曼编码有什么特点？

哈夫曼编码中每一个字符的编码都是前缀码，即对于每一个字符规定用0,1串作为其代码，并且要求任一字符的代码都不是其他字符代码的前缀，这种编码就是前缀码。例如a的前缀码为0，那么只要是这种0就一定是a，不会产生歧义。例如001011101就唯一地表示为aabe，不会产生其他歧义字符串。编码的这种前缀性质就会非常利于对一个01串进行解码，并且平均长度也很好计算为：

$$B(T)=\Sigma{f(c)dT(c)}$$

而哈夫曼编码就是一种是平均码长达到最小的前缀码编码方案。

思考：怎样构造哈夫曼编码？

哈夫曼编码的构造是使用二叉树构造的，考虑一个问题，越是处于深层的字符其相对应的01串长度也就会更长，而使用频率更频繁的字符其相对应的位数应该越小越好，所以我们很容易就想到了一种贪心法构造哈夫曼编码，即尽量每次选取使用频率更小的字符来当做叶子节点，而频率更大的字符则尽量在树的上层，所以就有了如下的构造方法：

1. 根据n个权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。
2. 在F中选取两棵根结点的权值最小的树作为左右子树来构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树结点的根结点的权值之和。
3. 在F中删除这两棵树，同时将新得到的二叉树加入F中。
4. 重复（2）和（3），直到F中只含一棵树时为止。称这棵树为最优二叉树（或哈夫曼树）。
5. 如果约定将每个节点的左分支表示字符‘0’，右分支表示字符‘1’，则可以把从根节点到某叶子节点的路径上分支字符组成的字符串作为该叶子节点的编码。

哈夫曼树算法是一种以自底向上的方式构造表示最有前缀码的二叉树T。算法以|C|个叶子节点开始，执行|C-1|次的合并运算后产生最终所要求的的树T。相信你也看不懂介绍，直接上例题✍。

对于上面的表格，那个哈夫曼编码是怎么得到的，我们做一次推导：

首先我们将5个字符和其使用次数一次从小到大列出，然后按照贪婪策略，每次选取两个小的合并来当做底层树枝，相对应的他们的01串位数也就相对应的会更长。这里先选取了f和e进行合并，合并后的使用次数为14，然后在观察发现，c和b是使用次数最少的，所以合并c和b,次数为25，此时14是由f和e合并得到的，25是由a和b得到的，每次合并后都要重现从小到大排列，此时还剩下14,16,25,45,我们接下来要合并的是14和16得到30，然后重排列后为25,30,45，合并25和30得55，最后45和55得到根节点，根节点代表所有字符频率之和。最后树就是右下角这个样子，由于每次都是从小到大排序，所以检查是不是左边的节点永远小于右边的节点，是不是上一层的节点永远比下一层的节点权值要大，这样我们就实现了权值大的节点即使用频率多的字符更靠近上层，相对应的其01表示串的位数也就少了，最后按照左0右1编码就得到了a是0，b是101，c是100，d是111，f是1100，e是1101，确实和表中的前缀码一致。

思考：时间复杂度是多少？

这里的每次从小到大重新排列我们可以采用一种较为巧妙的方法进行选取合并从而不用多次进行排序，那就是使用优先队列，权重越大选取合并优先级就越低。这样每次合并以后的频率插入优先队列Q中就会自动拥有一个被选取的优先级顺序。那么此时唯一会消耗大量时间的就是插入和删除以及n-1次合并的时间了，最终时间复杂度可以控制到O(nlogn)。

拓扑排序

定义：什么是拓扑排序？

任务的先后顺序可以用有向图来表示，成为AOV（Activity On Vertex)。有向图的顶点代表任务，有向边(i,j)表示先后关系：任务i完成以后才能完成j，即i是j执行的前提。根据这种AOV网络我们要对任务进行排序使得排序序列的先后关系与AOV网定义的先后关系一致。这种根据任务的有向图建立拓扑序列的过程就称为拓扑排序。所以拓扑排序是根据有向图即AOV神经网来进行节点排序。

下图就是一个AOV神经网络图：

1和2入度为零，说明没有前提任务节点，3的入度为1其前提任务节点就是先驱节点1,4入度为3说明其有三个前提任务节点，即需要1,2,3都完成以后才能开始执行任务4，所以其前提任务节点是1,2,3。以此类推。

首先对于每个节点进行逐一检验的方法肯定是行不通的，双重循环时间复杂度过高O(n!)。这里我们采用贪心思想进行拓扑排序。贪心策略从空集开始进行节点选取，每步产生拓扑排序序列中的一个顶点w，那么这个节点w该如何选取呢？

思考：怎样实现贪心策略？

1. 在尚不在拓扑排序序列中选择一个节点w，他需要满足的条件是他前面的任务都已经完成了，即其所有先驱节点v都已经在产生的拓扑序列中（或者无先去节点也可以），然后如果满足条件就将其加入到拓扑序列中。所以这个节点的入度一定为0，这样才代表其没有先去节点或者先去节点任务已经完成。
2. 用减节点入度的方法来更新，每次选取一个节点加入拓扑序列中意味着这个任务现在被完成了，那么从这个节点w所连接的后继节点q看来就是他少了一个前提任务，所以前提条件少了一个，对应的就是q入度减1，所以w所连接的后继节点相应的入度减1，当后继节点q的入度变为0时，则意味着他的所有先驱任务节点都已经完成，则他就也像w一样可以加入到拓扑序列中去了。

伪代码

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

void topologicalOrder(int *theOeder){
   	//计算每一个顶点的入度（需要用到邻接矩阵）
  	//将入度为0的节点push到栈中
    while(stack!=NULL){
        //当栈不为空时，即还有可以执行的任务
        //栈内所有节点入度均为0，表示现在都等待执行
        //随机任取一个入度为0的节点放入拓扑序列中
        //将其后继节点的入度-1
        //如果有新的入度为0的节点出现，将其放入栈中
    }
    //如果还有剩余的没进入栈（当然也就没进入拓扑序列)中的节点
    //那么他的入度还不为0
    //所以有向图内存在环路
}

所使用到的邻接矩阵：

有向图带有方向表示的邻接矩阵，由于没有权重路径长度一说，所以相连通就为1，不通就为0即可。至于所说的存在环路的情况：

就像这种情况，各个任务互为先决条件，很明显有问题，是一种悖论，不是题错了就是你写的邻接矩阵出错了。

时间复杂度

这里如果使用的是邻接矩阵那么就为O(n^2)，如果使用的是邻接表，那么时间复杂度仅为O(n+e)，首先无论是哪种初始化一定是O(n)，而计算入度的时候，如果使用的是邻接矩阵，那么需要二重循环所以时间复杂度为O(n^2),而如果使用的是邻接表，那么所用的时间仅为O(n+e)，进出栈(如果没有环路的话),时间复杂度为O(n),对于邻接矩阵，每次修改入度时时间复杂度为O(n)，而使用邻接表时每步修改时间为O(节点w的出度)。所以时间复杂度为最高次项决定所以分别为O(n^2)和O(n+e)。并且有所有节点的出度之和等于有向图的边数。

单源最短路径问题（迪杰斯特拉算法）

任意给一个有向图G，他的每条边都有一个非负的权值a[i][j],路径的长度就是各边的权值之和。单源最短路径问题就是给定一个源节点（即起始点），找出s到图中所有其他节点的最短路径，注意是都从s出发，所以就是找最短路径问题，只不过这次是一次性找到所有s到其他点的最短路径。这个和上面的最短路问题不太一样，原因是他可以中途对比几条从s到终点q的路径然后选出最优路径，当然局部来看还是在每次找最短子路径的贪婪策略。这种题模型经常在实际生活中出现，例如网络中传输数据流时，要消耗网络的带宽和存储资源，使用跳数少的路径节省网络资源等，并且IP路由使用最短路算法（OSPF），因为IP路由表按目的节点索引（查找），所以，OSPF协议就是使用的该算法求出网络中目的节点到任意节点的最短路径。

思考：怎样具体实现迪杰斯特拉算法？

1. 维护一个集合S，该集合中源节点到其他节点的最短路已知，即记录已经求出的s到其他节点的当下最短路径值，初始化时为空。
2. 从V-S结合中找一节点V，满足源节点到该节点距离最小。
3. 更新V的临界点的到源节点的距离值。

具体实现如下图：

首先有向图如下，我们建立一个索引表Q用来存储中途最短路径值，S用来存储节点，我们以求A为源节点为例，首先S初始化为空，即默认A此时到其他的点距离为∞。

然后寻找A所能直接到达的点并选取最小的距离，这个最小距离肯定是A到最相邻的点的最优值，而其他较大的就有可能会产生更小的最小路径。

此时A与B,C直接相连，且到达C的距离最短仅为3，而到B的距离为10，所以C和A肯定已经是最短距离了，而B则未必，可能存在一条经过C的更短路径可以到达B。至于为什么C一定是与A连接的最短路径了呢？想想也知道，如果不是，那么也就是说可能存在一条经过B的到达C的更短路径，但是A到B就已经10了，所以根本不可能，将B,C两个索引表建立新节点并更新A到这两个节点的当前值10和3，并且将C加入到S中，然后来到C点。

那么接下来看C与B和D,E相连，且值分别为4,8,2，所以相应的A到B，D,E的值分别更新为7,11,5，发现A到B的路径确实变短了，但是此时A到E的路径最短，所以A到E的路径已经是最优的最短路径了。而A->B,A->D则可能还会存在更短的路径。先更新邻接表：

此时A到E的距离最短，所以将E加入集合S，并且来到E节点：

此时观察E直接相连的节点有D，所以E到D的距离为9，那么A到D的距离为14（如果要路过E的话）比A->C->D要更长，所以不更新D的值，而B的值也未发生变化：

此时有A->B,A->D两条路，A->B更短，所以此时可以确定A->B的最短路径长度就是7了，即A->C->B，然后将B加入到集合S，然后来到节点B。

此时观察B的直接相连节点有D,C，但是B就是从C来的，且已经将C加入到集合S中了，所以只观察为将入到集合S的D节点，发现B到D的路径长度为2，所以A->D的路径长度为9（如果按照A->C->B->D）的话比11要短，所以更新D的节点，并将D加入到集合S中去。

此时发现所有节点都已经加入到S中去了，所以算法结束，得到了集合S，和一个更新完后的邻接表，那么这两个数据结构有什么作用呢？

思考：我们从两个数据结构表中能够知道那些信息，尤其是S？

首先邻接表就不用想了，肯定是记录的是A到其他各个点的最短路径长度，那么S有什么用处呢？我们发现在集合S中距离A越近的点距离也相对应的越短，所以我们通过邻接表和S就可以轻松知道各个点与A节点的定性和定量的最短路径距离了。

小试牛刀：用迪杰斯特拉算法计算下面这两个图的单源最短路径。

1

2

思考：对于没有权重的有向图能否也使用迪杰斯特拉算法？

实际上可以，这里我们以中途经过的节点数目来表示路径长度。如下图：

这里我们寻找以a为起点的单源最短路径。那么a直接相连的是b,d且路径长度均为1，此时这两个实际上都已经是a到这两个点的最短路径了我们随意选取一个点作为下一步的出发点其实都可以，这里我们以b为例。

此时在b点看来，直接相连的有c,e且均为2，此时a到c和e都已经是最短路径长度了，即a到c和a到e的路径长度均为2。

这里a->b的路径是最短的，所以接下来我们讨论b点。（即每次都选择已知最短的路径所连接的点）

在d点看来他只与e点相连间距为1，所以a->d->e的路径长度也是2并没有改变a->e的最短路径长度。此时我们还剩两个点c,e可以讨论，因为都是2又已经是已知的最短路径了，这里就接下来讨论c。

发现c也是只与e点相连，并且经过c点到达e点距离为3比a->b->e或者a->d->e还要更长，所以不改变a->e的最短路径，什么也不更新，直接将c接入到集合S中，然后此时只剩下了e点，所以接下来讨论e点。

e点与g,i直接相连，并且a->g和a->i的距离都是3，所以此时选择两个中的任意一个都可以，所以在这里我们选择g。此时

g连接的有f点，并且a->f现在已知的最短距离为4，而a->i仅为3，所以接下来讨论i点。

发现a->i->h的距离为4，所以此时f,h任取。我们这里接下里讨论f点，发现f->h为1，所以a->f->h距离为5比a->i->h距离还要长，所以不更新a->h的距离，所以直接加入f点到集合S然后讨论h点，发现所有点都已经走过了，算法结束。

我们发现对于无权值的有向图来说，每次产生的新节点其实距离都是相同的，因为都是加1，所以每次得到的第一个值大概率就已经是最短路径了。

总结

对于迪杰斯特拉算法，首先需要规定的就是有向图的权重值必须为非负的，首先是因为在现实生活中负的权值没有意义也不可能存在，其次对于负权值的情况会出现严重的bug,因为会导致出现反复循环走一种越走路径越短的闭合回路的情况。并且我们发现迪杰斯特拉广泛应用的原因不仅仅是因为其操作简便，思路简单，更重要的是使用贪心法得到的却一定是整体最优路径，即贪心解与最优解无偏差，误差为0。

最小生成树问题

具有n个顶点的连通的无向图G，图的每条边e有一个非负权值c(e)，也称为成本，求有最小成本的生成树。每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使得他们形成G的最小生成树。我们将采用两种不同的贪心策略选择这n-1条边，这两种贪心策略对用求解最小生成树的两个算法：克鲁斯卡尔(Kruskal’s)算法和普里姆(Prim’s)算法。

克鲁斯卡尔算法

贪心策略，每次都选取权值c(e)最小的且不和前面所选择的边构成回路的边e。上述算法要求按权值从小到大对边排序。如下图演示：

如上面所示，我们每次都尽量先选择权值小的边进行连接，并且要满足和前面的边不构成回路。最后检验时可以看是否是n-1条边。总体来看，非常好理解。并且这种算法同样是贪心解即为整体最优解，证明略。对于该算法，动态产生的子树，需要反复进行union和fond操作，因此使用union-find数据结构（并查集）最合适，初始时为单个顶点的集合，对每条边做两次find找到边的端点所在的集合，如果两个端点在同一个集合（形成回路了）就舍弃该条边，否则就将2个集合合并（union操作）。这样算法复杂度可控制在O（n+eloge)内。

小练习：构造如下图的最小生成树

普里姆算法

普利姆算法也很好理解，简单来说就是一条路走到黑，每次都以选取的下一个节点为起点寻找还可以走的最短的路径，如果只剩一条路可走，那无论权值多大都是走这条路经。如下图演示：

和克鲁斯卡尔算法演示的图一样。

就如上面偶说的那样，它区别于克鲁斯卡尔算法，当选去了1->6后并没有选择更短的3->4，而是在6的基础上继续走可以选择更短的路径。虽然与克鲁斯卡尔算法略有区别，但是最终的结果是相同的，都是贪心解等于最优解。

偶图覆盖问题（二分覆盖）

偶图是一个无向图，他的n歌顶点分为了集合A和集合B，且同一集合中任意两个顶点无边相连。A的一个子集A’覆盖集合B当且仅当B中的每一个顶点都至少和A’中的一个顶点相连，覆盖A’的大小用A’所含有的顶点数目表示，我们要寻找最小的覆盖的问题就是偶图覆盖问题。

例如面这道例题：有17个顶点分为两部分，其中上部分为集合A={1,2,3,16,17}，B={4,5,6,7,8,9,10,11,12,13,14,15}

那么很明显覆盖首先需要包括B中的所有顶点，子集A’={1,16,17}就已经覆盖了B中所有的点了，所以这就是B的最小覆盖。而单独来看1覆盖{4,6,7,8,9,13},16覆盖{5,6,8,12,14,15}，17覆盖{4,9,10,11}。那么怎么找到这个最小覆盖呢？

思考：怎样寻找到最小覆盖？

很简单，就是使用贪婪策略：每次都选取A中能够覆盖更多的B中还没有被覆盖的顶点的顶点，例如上题中，一开始A’为空集，覆盖了0个B中节点，然后1是覆盖最多剩余节点的顶点{4,6,7,8,9,13}所以讲1加入到集合A’中，此时剩余节点还有{5,10,11,12,14,15},而16是覆盖剩余节点最多的顶点{5,6,8,12,14,15}(一定要注意是剩余节点的个数，已经覆盖过得对结果没有影响)，然后最后是顶点17。

连续背包问题

与0/1背包问题不同的是此时可以连续性的装入，即按比例装入，那么贪婪政策每次都使用更大效益密度的物品装入直至不能再装入物品即可。并且易证得此时贪婪解就是最优解了。

小作业

Questions

1. 用1-优化算法求解以下0/1背包问题，已知：n=8,[16,20,4,15,25,10,5,8],p=[100,200,50,90,175,50,20,60],c=70。

2. 

   

   写出C语言代码。

Answers

1. 

2. 代码如下

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

   #include <bits/stdc++.h> using namespace std; //自定义一个物品结构体 struct Goods { //一件商品属性 //花费 double cost; //幸福感 long long int happy; //效益密度值 double p; }; bool cmp(Goods a, Goods b) { //按效益密度值排序 return a.p > b.p; } int main() { int t; cin >> t; while (t--) { int money, num; cin >> money >> num; Goods goods[num]; for (int i = 0; i < num; i++) { cin >> goods[i].cost; //存价格 goods[i].cost *= 0.9; //更新价格为9折 } for (int i = 0; i < num; i++) { //存开心程度 cin >> goods[i].happy; //计算开心密度并存储 goods[i].p = goods[i].happy / goods[i].cost; } //按效益密度值排序 sort(goods, goods + num, cmp); long long int ans = 0; /*for (int i = 0; i < num; i++) { if (money-goods[i].cost >= 0) { ans += goods[i].happy;//能装就装 money-=goods[i].cost; } else { break;//不装退出 } }*/ //1-优化才能得到正确答案 for (int i = 0; i < num; i++) { long long int tmp = 0; int cnt = money; tmp += goods[i].happy; cnt -= goods[i].cost; for (int j = 0; j < num; j++) { if ((j != i) && (cnt - goods[j].cost >= 0)) { tmp += goods[j].happy; cnt -= goods[j].cost; } } if (tmp > ans) { ans = tmp; } } cout << ans << endl; //输出结果 } return 0; }

总结

那么本次贪心思想算法分享就到此结束了，我们通过多个例题的学习对于贪婪算法有了更近一步的了解，最重要的是掌握哈夫曼树，0/1背包，最短路和单源最短路径以及两种最小生成树算法的理解与应用，当然拓扑排序和AOV神经网略也需要了解。那么希望你能有所收获😮。