第5 章
贪心算法
5.1 概 念
贪心算法与一般算法的不同之处在于它可以快速解决特定问题。贪心算法总是基于当
前情况,不考虑整体最优解,只考虑下一步的最优解。所以贪心算法在解决问题时,总是自
上而下、逐步迭代,每做一次贪心选择后,问题规模就会变小,直到问题的规模达到显而易见
的程度。
虽然每一次贪心选择都能使局部达到最优,但由此产生的全局解决方案并不一定是全
局的最优解。但是有时候可以通过各种方法来证明该贪心策略可以达到全局最优,或者达
到近似的全局最优。贪心算法的核心问题是选择可以为问题生成最佳解决方案的最佳度量
或特定的贪心策略。
5.1.1 贪心算法的基本要素
1.贪心选择
贪心选择性质,是指通过一系列局部最优选择或贪心选择,可以得到一个问题的整体最
优解。这是贪心算法可行的第一个基本要素。在贪心算法中,仅在当前状态下做出最好选
择,即局部最优选择。然后再解出这个选择后产生的相应的子问题。贪心算法通常以自顶
而下的方式进行,以迭代的方式做出相应的贪心选择,每做一次贪心选择就将所求问题简化
为规模更小的子问题。
2.最优子结构
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。运用
贪心策略在每一次转换时都取得了最优解。
5.1.2 贪心算法的基本思想
用局部解构造全局解,即从问题的某一个局部开始求解并向着总目标进行,以尽可能快
地求得更好的解。当某个算法中的某一步不能再继续前进时,算法停止。贪心算法思想的
本质就是分治,或者说,分治是贪心的基础。每次都形成局部最优解,即每次都处理出一个
最好的方案。
5.1.3 贪心算法的实现过程
从问题的某一初始解出发,循环找到能朝给定总目标前进一步的可行解的一个最优解
元素,直到达到总目标。由所有解元素构成的集合就是贪心算法的一个可行解。
102
算法设计与分析
5.1.4
适用条件
贪心算法的最终目的不是得到总问题的最优解,但对于某些问题,也可以总能求得整体
的最优解,这需要解决特定条件的问题,因此贪心算法不一定能找到解决总问题的最
优解。
只要能满足贪心算法的两个性质:贪心选择性质和最优子结构性质,贪心算法就可以
求出问题的整体最优解。即使对于某些问题,贪心算法不能求得整体的最优解,也能求出近
似整体最优解,如果对结果要求并不高时,贪心算法是一个很好的选择。
5.背包问题
2
5.2.1
问题描述
假设有一个最多能装
M
kg的背包,现在有
n
种物品,每件的重量分别是W1,W2,…,
Wn
,每件物品的价值分别为C1,C2,…,Cn
,需要将物品放入背包中,要怎样放才能保证背
包中物品的总价值最大。即背包问题如何选择装入背包的物品,使得装入背包的物品的总
价值最大? 但要注意在该背包问题中可以将物品的一部分装入背包。
问题分析如下。
首先对问题进行形式化表示。这里背包容量
M
>0,每个物品重量Wi
>0,物品价值
Ci>0 。要找出一个
n
元向量(x1,xn
其中,xi
是物品
i
装入背包中的百分比,0≤
xi≤1,1≤i≤n,要求:
x2,…,),
Σ(n) Wixi
≤
M
(5-1)
i=1
求解目标是:
C= Σ(n) Cixi
最大
i=1n
如果背包容量大于或等于要装入物品的总量,即ΣWi
≤
M
,则将所有物品全部装入
i=1
背包中为最优解,这时:
最优值为:
xi=1,1≤
i
≤
n
C= Σ(n) Ci
(5-2)
i=1
5.2.2
问题求解
用贪心算法解决背包问题的核心是如何选择贪心策略。下面以一个例子分析贪心策略
的选择,考虑以下背包问题。
M=20,=
n3
(C1,C2,C3)=(25,24,15)
(W1,W2,W3)=(18,15,10)
第5 章 贪心算法1 03
贪心策略1:
考虑使背包中物品价值增长最快,每次选择价值最大的物品优先装入背包。
该策略首先按照物品价值从大到小的顺序进行排序:
(C1,C2,C3)=(25,24,15)
优先把价值最大的物品放入背包。由于背包容量大于物品1重量,物品1全部放入背
包;背包剩余容量为2;然后查看排序序列中的下一个物品———物品2,由于背包剩余容量小
于物品2的重量,物品2只能部分放入背包,放入背包中的比例为2/15,此时有:
x1 =1, x2 =2/15, x3 =0
C =Σn
i=1
Cixi =25×1+24×2/15+15×0=28.2
贪心策略2:
考虑使背包剩余容量减少最慢,每次选择重量最轻的物品优先装入背包。
该策略首先按照物品重量从小到大的顺序进行排序:
(W3,W2,W1)=(10,15,18)
优先把重量最轻的物品放入背包。由于背包容量大于物品3重量,物品3全部放入背
包;背包剩余容量为10;然后查看排序序列中的下一个物品———物品2,由于背包剩余容量
小于物品2的重量,物品2只能部分放入背包,放入背包中的比例为10/15=2/3,此时有:
x1 =0, x2 =2/3, x3 =1
C =Σn
i=1
Cixi =25×0+24×2/3+15×1=31
贪心策略3:
考虑将单位价值最大的物品优先装入背包。
该策略首先按照物品单位价值从大到小的顺序进行排序:
(C2/W2,C3/W3,C1/W1)=(24/15,14/10,25/18)=(1.6,1.4,1.39)
优先把单位价值最大的物品装入背包。由于背包容量大于物品2的重量,物品2全部
放入背包;背包剩余容量为5;然后查看排序序列中的下一个物品———物品3,由于背包剩余容
量小于物品3的重量,物品3只能部分放入背包,放入背包中的比例为5/10=0.5,此时有:
x1 =0, x2 =1, x3 =0.5
C =Σn
i=1
Cixi =25×0+24×1+15×0.5=31.5
通过以上求解可知,不同贪心策略得到不同的解,贪心策略的选择决定了算法是否能够
得到最优解。
5.2.3 算法实现
viodKnapsack(double c[],double w[],double M,int n){
//C[1…n]存放n 种物品的价值,W[1…n]存放n 种物品的重量,
//M 表示背包所能承受的重量,x[1…n]表示每种物品放进背包的比例
double x[]; //x[1…n]表示每种物品放进背包的比例
按C[i]/W[i]将序列c 和w 从大到小排列
for(i=1; i<=n; i++) x[i]=0; //初始化
1 04 算法设计与分析
double cu=M; i=1;
while(W[i]<=cu){
x[i]=1; cu=cu-w[i]; i++;
}
x[i]=cu/w[i];
printf(w);
printf(x);
}
5.2.4 算法分析
算法的时间复杂度包括两部分:排序时间和求解时间。排序时间为O (nlog2n),问题
求解时间为O(n),因此算法总的时间复杂度为:
O(nlog2n) (5-3)
对于背包问题选择贪心策略1和贪心策略2不一定能找到最优解,选择贪心策略3一
定能找到最优解,下面给予证明。
证明:
设C1
W1>C2
W2>…>Cn
Wn ,x=(x1,x2,…,xn)是贪心策略3产生的解。
如果M ≥ Σn
i=1
Wi,即背包容量大于或等于物品重量总和,此时x=(1,1,…,1),物品全
部装入背包,x 一定是最优解。
如果M < Σn
i=1
Wi,则按照贪心策略3优先选择单位价值高的物品装入背包,这时一定
存在某个正整数j(1≤j≤n),使得:
x1 =x2 =… =xj-1 =1
0≤xj ≤1
xj+1 =xj+2 =… =xn =0
Σn
i=1
Wixi =M
ì
.
í
....
...
(5-4)
现假设x'=(x'1
,x'2
,…,x'n)是背包问题的最优解。
设存在一个k(1≤k≤n),对于(1≤i≤k-1),有xi=x'i,xk ≠x'k
(1)如果xk >x'k :
由于Σk-1
i=1
Wixi =Σk-1
i=1
Wix'i,所以
Σk
i=1
Wixi > Σk
i=1
Wix'i (5-5)
而Σn
i=1
Wixi =M ,所以Σk
i=1
Wixi ≤ M ,Σk
i=1
Wix'i< M ,因此x'k+1,x'k+2,…,x'n 必不全
为0。
因此可以增大x'k 的值,减少x'k+1,x'k+2,…,x'n 中某些项的值,同时保证Σn
i=1
Wix'i=M ,
第5 章 贪心算法1 05
得到一个新解x″。由于新解将x'k+1,x'k+2,…,x'n 中的容量调整到了x'k,Ck
Wk >Ck+1
Wk+1>Ck+2
Wk+2>
…>Cn
Wn ,因此新解x″优于最优解x',这与假设矛盾,因此满足xi =x'i(1≤i≤k-1),xk >
x'k 的最优解x'不存在。
(2)如果xk <x'k :
如果xk =0,按xi 定义,一定有Σk-1
i=1
Wixi =M ,又由于当1≤i≤k-1时有xi =x'i,所
以Σk-1
i=1
Wix'i=Σk-1
i=1
Wixi =M ,则x'k =0,与假设xk <x'k 矛盾,所以xk 必大于0。
如果xk =1,由于x'i的取值范围为0~1,所以这时xk <x'k 也不成立,因此xk 必小于1。
如果0<xk <1,则必有x1 =x2 = … =xk-1 =1,xk+1 =xk+2 = … =xn =0。所以
Σk
i=1
Wixi =M ,如果xk <x'k ,则有Σk
i=1
Wix'i>M ,背包内物品重量超过背包容量,因此命题
也不成立。
因此,xk <x'k 不成立。
因此,最优解x'不存在,x 即为问题最优解。
5.3 带时限的作业调度问题
5.3.1 问题描述
给定作业J1,J2,…,Jm ,各作业的处理时间为t1,t2,…,tm ,各作业的完工时限为d1,
d2,…,dm ,作业Ji 若能在时限di 之前完成,能获得利润pi。假设只有一台处理机为这批
作业服务,处理机一次只能运行一个作业。
问题是:怎样选择作业子集J,使J 中的作业都能在各自的时限内完工,且获得的利润
最大?
5.3.2 问题分析
问题是从作业集合中,选择一个子集合J=Ji1,Ji2,Ji3,…,使得集合J 中的作业都能
在各自时限di 内完成,使得收益ΣJi∈J
pi 最大,如图5-1所示。
图5-1 带时限的作业调度问题
设fi 是作业Ji 的完工时刻,作业子集中J 的作
业Ji 需满足fi≤di。假设所有作业从时刻0开始运
行,则必有di≥ti。
为了简化问题,只讨论ti =1的情况,这时所有
作业的执行时间都只占用一个单位时间,且di 为正
整数。例:m=4,p=(115,70,85,100),d=(2,1,2,1)。
从时限d 可知,一台处理机在时限内最多可处理两个作业,其利润表如表5-1所示。
1 06 算法设计与分析
表5-1 作业调度表
序 号作业子集作业处理顺序利 润
1 {J1,J2} J2,J1 185
2 {J1,J3} J1,J3 或J3,J1 200
3 {J1,J4} J4,J1 215
4 {J2,J3} J2,J3 155
5 {J2,J4} 不可调度
6 {J3,J4} J4,J3 185
不同的作业选择有不同的收益。
5.3.3 以利润最大作为贪心策略
以利润最大作为贪心策略,可以保障利润大的作业优先进入加工队列中。
1.算法过程
以利润为最优化量,按利润从大到小选择作业,其过程如下。
(1)初始化集合:J=.,Σpi =0。
(2)设子集J 中已有k-1个作业Ji1,Ji2,…,Jik-1,它们是一个可完工的作业子序列,
在剩余的作业中选择利润最大的作业Jik 加入J 中。
(3)判断作业Jik 加入后,判断Ji1,Ji2,…,Jik-1,Jik 是否是一个在时限内可完工的子
序列,如果不是,从集合J 中删除作业Jik 。
(4)重复步骤(2)和(3),直至完成所有作业的判断。
在上述步骤中,判断一个作业Jik 加入后,序列Ji1,Ji2,…,Jik-1,Jik 是否是一个在时限
内可完工的子序列,是一个难点。
如果用穷举法进行判断,其算法时间复杂度为1!+2!+…+n!,代价较高,可以采用如
下方法判断。
将J 中作业按时限非递减顺序排列,使得:
di1 ≤di2 ≤ … ≤dik
又因为每个作业需要执行一个单位时间,所以如果dij≥j(1≤j≤k)成立,则J 是可完
工的作业子序列。
2.算法实现
void Js1( ){
scanf(p,d,n); //假设p[1]>=p[2]>=….>=p[n]
J[0]=0; D[0]=0;
J[1]=1; k=1; //J[i]表示第i 个加入J 的作业号,k 为J 中已有的作业数
for(i=2; i<=n; i++){
r=k;
while(D[J[r]]>D[i]&& D[J[r]]!=r) r--; //测试能否加入作业i
第5 章 贪心算法1 07
if(D[i]>r){
for (h=k; h>=r+1; h--) J[r+1]=J[r]; //加入
J[r+1]=i;
k++;
}
}
}
5.3.4 以最大时限作为贪心策略
以作业最大时限作为贪心策略,可以保障时限大的作业优先进入加工队列中,其过程
如下。
(1)令d=1m≤ia≤xn
di,称d 为该作业集的最大时限。由于每个作业执行时间为1,因此最
优调度集合J 中最多包含d 个作业。
(2)初始化作业集合J,此时作业集合J 为空,如图5-2所示。
(3)获取时限为d 的作业集合,取集合中利润最大的作业放入时限为d 的位置,如
图5-3所示。
图5-2 初始时作业集 图5-3 一次操作后作业集
(4)获取时限大于或等于d-1且未放入J 中的作业集合。如果集合不为空,取集合
中利润最大的作业放入时限为d-1的位置。如果集合为空,则d-1位置无作业可调度,
如图5-4所示。
(5)获取时限大于或等于d-2且未放入J 中的作业集合。如果集合不为空,取集合
中利润最大的作业放入时限为d-2的位置。如果集合为空,则d-2位置无作业可调度。
(6)重复上述过程,直至时限为1。此时作业集合J 如图5-5所示。
图5-4 二次操作后作业集 图5-5 调度后作业集
该作业集合(作业序列)则为问题的解。
算法实现
void Js2( ){
scanf(n,p[1..n], d[1..n]);
d=max{d[1],d[2],…,d[n]};
for(i=0; i<=d; i++) s[i]=.;
for(i=1; i<=n; i++) s[d[i]]=s[d[i]]∪{Ji};
//将时限为i 的作业放入集合s[i]中
k=0;
for(i=d; i>=1; i--){
1 08 算法设计与分析
if(s[i]≠.){
设j 是s[i]中利润最大的作业号;
J[k+1]=j ;
s[i]=s[i]-{ Ji}; //从时限为i 的作业集合s[i]中选入J 中作业删除
k++;
}
s[i-1]=s[i-1]∪s[i]; //合并候选作业集
}
}
5.3.5 快速调度法
设b=min(n,d),其中,n 为所有作业数,d=1m≤ia≤xn
di。
如果b=n<d,将作业时限大于b 的时限值设为b,则任何最大利润的可完工子序列中
作业个数必不大于b,任何可完工的作业子序列中最多只包含一个时限为1的作业;最多包
含两个时限不大于2的作业;……;最多包含b 个时限不大于b 的作业。
快速调度法是5.3.3节以利润最大作为贪心策略的一种改进贪心算法,以减少数据挪
动的次数。
该算法用数1,2,3,…,b 对应时间区间[0,1],[1,2],…,[b-1,b],按利润pi 大小排
出非递增序列S,依次从S 中取出pi,找出[0,1],[1,2],…,[di-1,di]中还没有分配给任何
作业的最大区间分配给作业i,这样作业被安排到不能再推迟的那个时间内执行,以保证安
排更多的作业。
例如,有5个作业J1,J2,J3,J4,J5,其时限分别为(2,2,1,1,5),每个作业若能在规
定的时限内完工,可获得的利润分别是(120,115,70,55,10)。此时b=5,区间如图5-6
所示。
这5个作业正好是按照非递增序列排序的,因此先安排作业J1,由于作业J1 的时限为2,
把它安排在区间[1,2],此时如图5-7所示。
图5-6 区间划分图5-7 一次调度后
接着安排作业J2,作业J2 的时限为2,由于区间[1,2]已安排了作业J1,所以作业J2
只能安排在区间[0,1]。
由于作业J3 和J4 的时限为1,应该安排[0,1],由于该区间已经安排了作业J2,所以
作业J3、J4 不能按时完工。
作业J5 时限为5,安排在区间[4,5],安排后的最优作业调度序列如图5-8所示。
图5-8 调度后
第5 章 贪心算法1 09
算法实现
void Js3( ){
read(n,p,d); //p[1]≥p[2]≥…≥p[n]
b=min{n,max{d[i]}};
for(i=1; i<=b; i++) J[i]=0; //i 表示时间区间,0 表示尚未分配出去
j=1;
for(i=1; i<=n; i++){
k=d[i];
while(k>0)
if(!J[k]) {J[k]=j; k=0; }
else k--;
j++;
}
}
5.4 最佳合并顺序
5.4.1 问题描述
有n 个有序子序列S1,S2,…,Sn ,要求通过两两合并的方法把这n 个子序列合并成一
个有序的序列。试设计一个算法确定合并这个序列的最佳合并顺序,使所需的总比较次数
最少。
5.4.2 问题分析
合并两个长度分别为m1、m2 的子序列,在最坏情况下需要m1+m2-1次比较。
对给定的n 个有序的子序列,若采用两两合并的方法,由于每个子序列的长度不同,不
同的合并顺序所用的时间是不同的。
例如:
n =3, |S1|=80, |S2|=50, |S3|=40
合并方法如下。
(1)(S1+S2)+S3,比较次数:(80+50-1)+(130+40-1)=298。
(2)S1+(S2+S3),比较次数:(50+40-1)+(90+80-1)=258。
(3)(S1+S3)+S2,比较次数:(80+40-1)+(120+50-1)=288。
我们发现第(2)种合并次序需要的比较次数较少。
通过观察发现,对给定的n 个序列,共需要n-1次合并,要减少合并过程中的比较次
数,就应减少中间结果的长度。因此,可以考虑按序列长度由小到大的顺序合并。
5.4.3 问题求解
假设有5个序列,这5个序列的长度分别为50,70,80,90,100,图5-9表示两种不同合
并顺序的二叉树,其中,每个叶子结点表示一个原始序列,每个内结点表示一次合并,如
图5-9所示。
1 10 算法设计与分析
图5-9 两种不同合并二叉树
二叉树中所有结点的度或为0,或为2。表示合并顺序的二叉树中总有n-1个内结点,
每个内结点表示一次合并,树中表示的总比较次数为各内结点中数值之和减去内结点数。
由于内结点数固定为序列的长度减1,因此可以用内结点中的数值之和表示比较次数。而
内结点中的数值正好为各叶子的加权深度。因此,求最佳合并顺序问题等价于求加权深度
最小的二叉树。
求加权深度最小的二叉树的过程如下。
(1)为原始序列中的每一个序列建立一棵二叉树,这些二叉树构成一个树的集合L,每
棵二叉树的根即叶子。WEIGHT(T)是每棵二叉树的权,定义为每个序列的长度。
(2)从L 中找出两棵权值最小的树分别作为一棵树的左右儿子,构成一棵新的树,并从
L 中删去左右儿子。新树的权WEIGHT(T)是它的左右儿子的权之和。
(3)重复步骤(2),直到L 中只有一棵树为止,这棵树表示了合并顺序。
5.4.4 算法实现
TreeNode OMTree(int[]w){
PriorityQueue<TreeNode> queue =
new PriorityQueue<>(w.length,new Comparator<TreeNode>(){
public int compare(TreeNode t1,TreeNode t2){
return t1.val-t2.val;
}
}); //将所有结点存入优先权队列,按照权值递增排序
for(int i=0; i<w.length; i++){
queue.offer(new TreeNode(w[i]));
}
while( queue.size()>1 ){ //构造二叉树
TreeNode node1=queue.poll();
TreeNode node2=queue.poll(); //弹出最小的两个结点
TreeNode father=new TreeNode(node1+node2); //构造父结点
father.left =node1;
father.right =node2;