cumt算法设计与分析期末考速通笔记（3）｜贪心算法

1 贪心策略与适用条件 #

贪心法每一步按某个规则选择当前最有利的方案。必须说明规则为什么能产生整体最优解；算对一个例子不足以证明正确，一个反例就能否定某种策略的普遍正确性。

以下排序均可用归并或堆排序保证最坏O(nlog n)。若输入已按对应关键字排序，排序可省略。

2 排队最小等待时间 #

条件与例题 #

所有人同时到达，只有一个服务窗口，目标是总等待时间或平均等待时间最少。等待不含本人服务时间。

服务时间为6、2、4、1，按升序排为1、2、4、6：

总等待为11，平均为11/4=2.75。最后一人等待7，完成服务时经过13，不要混用。

伪代码 #

按服务时间升序排列，保留人员编号
elapsed=0；total=0
依次遍历每个人：
    total=total+elapsed
    elapsed=elapsed+当前人的服务时间
返回顺序、total以及total/人数

正确性与复杂度 #

相邻两人耗时a>b时，把短者换到前面，两人的总等待减少a-b，后续人的开始时间不变。消除所有逆序即得到升序。

时间：排序O(nlog n)+累计O(n)，合计O(nlog n)。先累计等待，再加本人的服务时间。

3 最少区间覆盖 #

条件与规则 #

用尽可能少的区间连续覆盖[start,end]，可以重叠，不能留下空隙。区间只覆盖两个端点不够，必须覆盖中间全部位置。

当前已覆盖到cur：先找左端点≤cur的候选，再选择其中右端点最远的区间。

例题 #

目标：[0,10]
区间：[0,3]、[0,5]、[3,7]、[5,9]、[7,10]

结果为[0,5]→[5,9]→[7,10]，共3个。覆盖到5时不能直接接[7,10]，否则5到7有空隙。

变量与伪代码 #

最少覆盖(A,start,end)：
    将A按左端点升序排序
    cur=start；i=0；count=0
    当cur<end：
        far=cur
        当i<长度(A)且A[i].左端点≤cur：
            far=max(far,A[i].右端点)
            i=i+1
        如果far==cur：返回-1
        cur=far
        count=count+1
    返回count

具体执行与失败条件 #

上例排序后下标0到4依次对应五个区间：

本轮筛选时cur不变，只更新far。筛选完才更新cur并将count加1。检查多个候选不等于选择多个区间。

far==cur表示本轮无法向右推进。 例：[0,4]、[5,10]覆盖[0,10]。第一轮到4；第二轮far先设为4，下一段左端点5>4无法接上，far仍为4，返回-1。区间耗尽但cur仍小于end时也会如此。

正确性与复杂度 #

所有候选都能接上且都消耗一个名额，选得更远不会妨碍后续连接。在最优方案中，可用该候选替换下一段，使覆盖终点不提前且区间数不增加。

排序O(nlog n)，扫描O(n)。虽然有两层while，但i始终递增、不重置，每个区间最多检查一次，不能按n²计算。总时间O(nlog n)。

4 活动安排 #

条件与规则 #

同一时间只能参加一项活动，选择尽可能多项不冲突活动。约定开始时间等于上一项结束时间时可以相接。

先按结束时间升序，优先选结束最早的；后续只有开始时间≥lastEnd才选。

例题 #

按结束排序为B、C、A、D、E。选择B后lastEnd=3；C开始3≥3，选择并更新到5；A开始0<5，跳过；D开始5≥5，选择并更新到7；E开始6<7，跳过。

结果B→C→D，共3项。只按开始早选A，最多再接E，只得2项。

伪代码 #

活动安排(A)：
    如果A为空：返回[]
    将A按结束时间升序排序
    结果=[A[0]]
    lastEnd=A[0].结束时间
    对i=1到长度(A)-1：
        如果A[i].开始时间≥lastEnd：
            将A[i]加入结果
            lastEnd=A[i].结束时间
    返回结果

跳过活动时不更新lastEnd。 最终活动数为结果长度。

正确性与复杂度 #

结束最早者可以替换某个最优方案的第一项，且不会让后续可用时间减少。再对其结束后的活动重复同样选择。

归并排序O(nlog n)，一次扫描O(n)，总O(nlog n)；已按结束排序时为O(n)。

与覆盖的区别： 覆盖要求下一段左端点≤cur，选右端最远；活动安排要求开始≥lastEnd，选结束最早。两个条件方向不同，因为目标不同。

5 可分割背包与0–1背包反例 #

目标：容量内总价值最大。所有物品重量为正，允许按比例拆分时可按价值/重量降序贪心。

容量4，物品如下：

可分割：先拿完整A，再拿B的一半，价值5+1.5=6.5。

可分割背包(A,W)：
    按价值/重量从高到低排序
    剩余=W；总价值=0
    依次遍历每件物品：
        如果物品重量≤剩余：
            总价值+=物品价值
            剩余-=物品重量
        否则：
            总价值+=剩余×物品价值/物品重量
            返回总价值
    返回总价值

每单位容量优先留给价值更高者；可分割使最后一件可取部分。排序加扫描，时间O(nlog n)。

0–1背包中不能保证此策略最优： 若每件只能整件取或不取，先选A只能得5，剩余容量1无法再装；选择B+C恰好重4、价值6，优于贪心结果。

0–1背包的动态规划解法单独放在DP专题。

6 考场检查清单 #

• 先写目标，再写选择规则；不能混用排队、覆盖和活动安排的排序依据。
• 写出约束与失败情况；覆盖失败返回-1。
• 伪代码可使用中文配合if/while/return，不必写完整C++程序。
• 复杂度分清排序与扫描，先后执行相加。
• 正确性说明用交换或替换思路；仅举成功例子不能代替证明。

本篇持续更新。尚未整理的课件内容：最优装载、哈夫曼编码、单源最短路径、最小生成树、多机调度。