第六章 贪心

6.2 可分割物品的背包问题

描述：略

按性价比从大到小排序：$p_i/w_i$

6.3 带时限的作业排序问题[贪心版]

描述：作业 $i$ 必须在期限 $d_i$ 之前完成才能获取收益 $p_i$，且完成每个作业只需1个单位时间（贪心法的前提）

分支限界版 => 9.3

6.3.1 朴素算法

思路：优先安排收益最高的作业，尽可能将其安排在最晚的可用时间点，从而为其他作业预留更多的早期时间段。

1. 按收益 $p_i$ 从大到小排序
2. 按顺序遍历所有作业
3. 从其截止时间向前查找可用时间 分配给该作业，若无空闲时间则跳过该作业。

首先按收益排序：
作业1：(2, 100)
作业4：(1, 27)
作业3：(2, 15)
作业2：(1, 10)

依次处理：
作业1(100)：可以安排在时间2
作业4(27)：可以安排在时间1
作业3(15)：没有可用时间，跳过
作业2(10)：没有可用时间，跳过
最终获得的最大收益为：100 + 27 = 127

习题6-3

最优解 5 6 3 2
最大收益 74

6.3.2* 改进算法

待补充

6.4 最佳合并模式

6.4.1 最佳两路合并模式（哈夫曼编码）

就是哈夫曼树求最小 WPL（带权外路径长度）

(20,30,30,10,5)

WPL = (5+10)*3 + (20+30+30)*2 = 205

6.4.2* 三(k)路合并 书p105/习题6-8

最佳合并模式_哔哩哔哩_bilibili

-, 视频播放量 47、弹幕量 0、点赞数 0、投硬币枚数 0、收藏人数 0、转发人数 0, 视频作者 亦是远方, 作者简介 一个程序员，相关视频：打算法竞赛的好处.jpg，阶跃点求解0-1背包问题，“还记得你的第一个helloworld吗”，马士兵预测未来3-5年即将淘汰的编程语言（Java、golang、php、C#...）,没项目、没经验、没技术？马士兵一个视频给你讲透计算机就业所有疑难杂症！，（英语原声）让你的电脑运行更流畅的奇妙算法，2025 Attention 再次炸裂！清华姚期智团队开源注意力新作，算力成本直降90%，拿下顶会！，南京邮电大学811数据机构-01-算法基础-线性表，算法讲解163【挺难】树上启发式合并的原理和相关题目，一口气搞懂二进制漏洞攻防对抗史！，爱因斯坦质问导师：你天天骂学生笨，你比我还聪明吗？回答我！

www.bilibili.com

补：虚节点，数量为 $(k-1) - (n-1) \% (k-1)$ 个
(3, 7, 8, 9, 15, 16, 18, 20, 23, 25, 28) => n=11,k=3, (n-1)%(k-1)=0，不用补；
(1，2，3，3，5，6，7，9) => n=8,k=3,(n-1)%(k-1)=1，补1个虚节点；WPL=66

6.5 最小代价生成树（最小生成树）

对于图 $G=(V,E)$

6.5.1 Prim

适用于稠密图
每次从已有点集合里扩展出一条最短的边

• 使用邻接矩阵时，时间复杂度 $O(V^2)$
• 使用邻接表 和优先队列 时，时间复杂度 $O(E*logV)$

6.5.2 Kruskal

适用于稀疏图
对边从小到大排序，依次加入边，每次加入都需要判环路

• 时间复杂度 $O(E*logE)$

习题6-9

明显是稠密图，选 Prim

6.6 单源最短路径

Dijkstra算法 边权非负

手写步骤：
又快又准做对考研真题，从考试的角度出发【Dijkstra】【单源最短路径】https://www.bilibili.com/video/BV1nh411Y7vj/

6.7 磁带最优存储

6.7.1 单带最优存储

说人话：
把 $n$ 个程序（线段）按某种顺序排列在一个磁带（数轴）上，程序不能重叠，保证磁带能放得下所有程序，要求平均检索时间（MRT）最小。
MRT = 所有程序的检索时间之和 $\div$ 程序个数
由于程序个数固定，所以 MRT 最小等价于检索时间之和最小。
检索时间 = 程序起点到磁带起点距离 $+$ 程序长度
每次检索都从磁带起点开始，所以离起点越远的程序检索时间越长。
各种排列方式参考：书p117 表6-5

贪心策略：按程序长度从小到大排序，依次放入磁带。

6.7.2 多带最优存储

现在磁带变成了 $m$ 个，其实也很简单：将程序$0$放在第一个磁带上，程序$1$放在第二个磁带上，程序$2$放在第三个磁带上...当 $m$ 个磁带都排完一遍，回到第一个磁带，继续顺次放程序。

#include <iostream.h>
void Store(int n, int m)     
{
     int j = 0; 
     for (int i=0; i<n; i++) { 
        cout << "将程序"<<i<<" 加到磁带" <<j<<endl; 
        j=(j+1)% m; 
     } 
     cout<<endl;
}

EX1: 最佳装载问题（习题6-17）

$n$ 个集装箱和一艘载重为 $C$ 的船。每个集装箱的重量为$w_i$。
求装载方案，使得装载的集装箱数量最大化，同时集装箱的总重量不超过船的载重限制 $C$。

贪心策略：每次都选择最轻的集装箱

(5) 最优方案：装 [2,3,4,5,6]

EX2: 活动安排问题（线段覆盖）

一个数轴上有n条线段，现要选取其中k条线段，使得这些线段两两没有重合部分，问最大的k为多少。线段的起点为活动的开始时间，终点为活动的结束时间。

贪心策略：每次选择结束时间最早的活动，以留下最多的时间给后续活动。

例：设待安排的11个活动的开始时间和结束时间按结束时间的非递减序排列如下：

贪心算法步骤

1. 首先将活动按结束时间从小到大排列。
2. 选择第一个活动。
3. 之后遍历剩下活动，若[活动B]的 开始时间 晚于 当前选择的[活动A]的结束时间，则选择[活动B]。

答案
${1,4,8,11}$

EX3: 多机调度问题

注意不要与动态规划的流水作业调度问题混淆。

作业数 $n$，机器数 $m$，如何分配作业让完成时间最短。

贪心策略：按 当前最短完成时间 分配作业到 最空闲的机器；优先分配处理时间较长的任务 以填满机器。

• 当 $n \leq m$ 时，直接为每个作业分配一台机器完成作业
• 当 $n > m$ 时，首先将作业按其执行时间从大到小排序，然后依次将作业分配给当前最空闲的机器

例：7个独立作业 $\{1,2,3,4,5,6,7\}$ 由3台机器 $M1, M2, M3$ 加工处理。

答案
$M1 \{4\}$
$M2 \{2,7\}$
$M3 \{5,6,3,1\}$
最优完成时间：17