算法设计与分析 课件 第五章 贪心法

计算机算法设计与分析第5章贪心法5.1.1部分背包问题给定编号1~n的n个物品，编号i的物品重量wi，价值vi，现用1个负重W的背包来装这些物品，在不超过背包负重的前提下，使得背包装入的总价值最大。与0-1背包问题的区别是这些物品可以分割后部分装入背包，分割后的物品重量价值比不变。5.1.1部分背包问题一个背包负重W=150的7个物品的部分背包问题：物品编号1234567重量wi35306050401025价值vi10403050354030贪心策略1：价值最大策略选择价值最大的物品，可以尽可能快地增加背包的总价值。但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证装入背包的物品总价值达到最大。按照物品价值从大到小排序，价值相同的重量小的优先，可选择4号物品、6号物品，2号物品、5号物品、7号物品（部分装入）。得到背包的总重量为50+10+30+40+20=150，总价值为50+40+40+35+20/25*30=189。物品编号1234567重量wi35306050401025价值vi10403050354030贪心策略2：重量最轻策略选择重量最轻的物品，可以装入尽可能多的物品，从而增加背包的总价值。但背包的价值却不能保证迅速增长，也不一定能保证装入背包的物品总价值达到最大。按照物品重量从小到大排序，可选择6号物品、7号物品、2号物品、1号物品、5号物品和4号物品（部分装入），得到背包的总重量为10+25+30+35+40+10=150，总价值为40+30+40+10+35+10/50*50=165。物品编号1234567重量wi35306050401025价值vi10403050354030贪心策略3：单位重量价值最大策略选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。将物品按照单位重量价格从大到小排序，可选择6号物品、2号物品、7号物品、4号物品和5号物品（部分装入），得到背包总重量为10+30+25+50+35=150，总价值为40+40+30+50+35/40*35=190.625。物品编号1234567重量wi35306050401025价值vi10403050354030结论显然，以上三种贪心策略中，每次选取单位重量价值最大策略使得装入背包的物品总价值最大。背包问题数学模型设xi表示编号为i的物品装入背包情况，0≤xi≤1。根据问题的要求，有如下目标函数和约束条件：证明贪心策略3正确性首先按照每个物品的单位重量价值vi/wi给物品重新排序，排序后的物品也重新编号为1~n，即i<j时有

。贪心策略：从单位重量价值最大的物品开始选择，若将这个物品全部装入背包后，背包没有超过其负重W，则继续选择下一个物品进行装入，当选择某物品装入背包后超过背包负重，则该物品采用部分装入方式将背包装满。证明贪心策略3正确性（1）存在包含单位价值最大物品的最优解。使用反证法来证明第一步选择，因为物品已经按单位重量价值递减排序且w1<W，则部分背包问题存在最优解v1x1+v2x2+...+vnxn。若x1=1，显然最优解包含单位重量价值最大的物品的结论成立。若x1<1，则将背包中重量等于(1-x1)w1的部分物品与物品1交换，这样背包的负重不变，但因，重样重量的物品1具有更大的价值，即等量交换后背包的总价值增加了，这与假设是最优解矛盾。如果w1≥W，则直接装入W重的第1个物品部分即为最优解，总价值为最优解包含单位重量价值最大的物品的结论成立!也即，贪心选择的第一步选择总是会包含在某个最优解中。（2）在完成第一步选择之后，子问题P'()与原问题P()还是同一类问题，意味着我们的选择没有改变问题的结构。令π'为子问题P'的最优解，π为原问题P的最优解，则π=π'+v1。证明贪心策略3正确性证明贪心策略3正确性还是使用反证法来证明这个结论，假设π不是原问题的最优解，原问题P的最优解为π*。根据第一步结论，我们知道最优解π*中一定含有v1，那么π*-v1就应该是子问题P'的解，π*-v1>π-v1=π'，这与π'为子问题P'的最优解定义矛盾。所以π=π'+v1不可能不是最优解，因此原问题的最优解等于子问题最优解加上第一个选择的物品价值。证明贪心策略3正确性（3）由以上两步证明知道，我们按照单位重量价值由大到小做出的每一步选择，都将原问题简化为一个与原问题相同形式的更小的子问题，使用数学归纳法可以证明这种贪心策略可以得到原问题的一个最优解。计算机算法设计与分析第5章贪心法5.2.1活动安排问题学校有n个分工会需要进行节目彩排活动安排，学校彩排舞台只有一个。每个分工会都有自己的一个空闲时间段，即每个分工会都给出自己可以进行彩排活动的一个起始时间和结束时间。而学校的舞台同一时间只能安排一个分工会入场进行活动。如何安排这次彩排活动，使得被安排的分工会尽可能多，没有能安排的分工会只能放到下次安排。活动安排问题设学校分工会节目彩排活动编号的集合为E={1,2,...,n}，第i个分工会节目彩排活动的起始时间为si，结束时间为fi，且si<fi。如果安排了第i个分工会进行彩排，则它在半开时间区间[si，fi)内占用舞台资源。当两个活动区间[si，fi)与[sj，fj)不相交，则称活动i和活动j是相容的，即si≥fj或sj≥fi，i≠j，活动i和活动j相容。活动安排问题是求解两两相容的最大活动子集S。活动安排问题分工会i1234567891011起始时间si130535688212结束时间fi4567891011121314贪心策略1：更早的活动起始时间优先策略，这样可以增大舞台资源利用率。按照活动的起始时间先后顺序选择活动。如表所示的11个活动，先安排活动3，则活动1、2、4、5、6、10与活动3均不相容；之后安排与活动3相容的具有更早起始时间的活动7，则活动8、9与活动7均不相容；之后安排与活动7相容的具有更早起始时间的活动11，安排结束。贪心策略1安排的相容活动集合S={3,7,11}。分工会i1234567891011起始时间si130535688212结束时间fi4567891011121314活动安排问题贪心策略2：更早的活动结束时间优先策略，这样可以下一个活动尽早得到安排。按照活动结束时间从小到大顺序选择活动，表中的活动已经按活动结束时间顺序从小到大排序。选择活动1，之后选择与活动1相容活动4，之后选择与活动4相容的活动8，最后选择与活动8相容的活动11，安排结束。贪心策略2安排的相容活动集合S={1,4,8,11}。分工会i1234567891011起始时间si130535688212结束时间fi4567891011121314活动安排问题活动安排问题贪心策略2的正确性证明：将n个活动按照其结束时间fi从小到大排序，排序后的活动序列还是按E={1,2,...,n}编号。第一次先选1号活动，然后接下来的每一步，从E中按顺序选出下一个相容的活动，直到E中所有活动都被检查过一遍。证明贪心策略2能得到活动安排问题的最优解，即考察如下问题：该算法执行到第k步时，选择了k个活动：i1,i2,...,ik，则存在最优解S包含这k个活动，即该算法执行的每一步的结果都是最优解的一部分。活动安排问题（1）设S是E的一个最优解且S={i1,...,im}。若最优解S的第一个活动i1≠1，由于活动1的结束时间是活动集合E中最前面的，因此

。这样，就将S中的i1换成1，得到S'：

由于

，因此S'中的活动也是相容的，而且活动数量与S中一致，故S'也是一个最优解。也即E中的第1步选择活动1肯定可以在一个最优解中。活动安排问题（2）采用数学归纳法证明，若第k步选择的活动ik在最优解中，则第k+1步选择的活动ik+1也在最优解中。归纳假设第

k步选择的活动ik在最优解中，可以表述为：前

k

步已经选择的活为i1,i2,...,ik，存在一个最优解S：第k+1步时，选择只能在待选活动集合E'中选取，所谓待选活动集合，即原集合E中去除已判为冲突的活动和已选择的活动后剩下的集合。活动安排问题①那么，B是E'（子问题）的一个最优解。若不是，假设E'的有解是B*，且B*>B，那么用B*替换B以后得到

，则S'>S，与S是最优解矛盾。故

②根据（1）的证明，贪心策略2的第一步选择结束时间最早的活动总是导致问题的一个最优解，故对于子问题E'存在一个最优解B'，包含子问题E'的第一个活动ik+1。因B'和B都是E'的最优解,B'=B，所以：S'和S是包含的活动数量一样的原问题的最优解，因此得证第k+1步选择的活动ik+1在最优解中。即按贪心策略2进行选择的活动必将导致问题的一个最优解是成立的。活动安排问题效率分析:问题的输入规模为n，按活动结束时间从小到大高效排序的时间复杂度为O(nlogn)，贪心算法选择活动n步即可完成，故T(n)=O(nlogn)。活动安排问题计算机算法设计与分析第5章贪心法5.2.2村村通最小成本问题村村通工程（通电、通水、通气、通网、通路等）是中国政府推行的一个旨在改善农村地区基础设施和信息化水平的工程项目。现某乡镇政府决定实现村村通公路，通过勘察已将各个村落之间的可修建道路成本数据统计在下表中，根据表中给出的数据，求使得每个村都有公路连通所需要的最低成本和具体修建线路。村落1111122345村落2345636456成本29845694635.2.2村村通最小成本问题用无向连通带权图G=（V，E）表示村落之间的道路数据及其公路修建成本，如图所示，各个村落为图G的顶点，村落之间有路连通用无向边相连，边的权值为修建村落公路的成本。村村通公路最小成本问题转化为求图G的最小生成树问题。5.2.2村村通最小成本问题对一个无向连通带权图G，如果G的子图G'是一棵包含G的所有顶点的树，则称G'为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。贪心策略1，Prim算法设图G=（V,E）是无向连通带权图，V={1,2,...,n}，E为边集，cost[i][j]记录顶点i到顶点j这条边的权值。Prim算法构造最小生成树的基本步骤如下：（1）置顶点集合S={1}；（2）只要S中顶点数目小于n，就作如下的贪心选择：选取满足条件i∈S，j∈V-S，且（i,j）边权值cost[i][j]最小，将顶点j添加到S中。这个过程一直进行到|S|=|V|时为止，选取到的所有边恰好构成G的一棵最小生成树。贪心策略1，Prim算法1SSSSSSPrim算法正确性证明对于k<n，存在一棵最小生成树包含Prim算法前k步选择的边。（1）首先证明k=1，存在一棵最小生成树T包含边e=（1，i），其中cost[1][i]是所有关联顶点1的边中权值最小的。Prim算法正确性证明设T是一棵最小生成树，且T不包含边（1，i），则T+（1，i）含有一条回路，删除回路中关联顶点1的另一条边（1，j）得到一棵生成树T'，如图所示。因cost[1][i]≤cost[1][j]，所以生成树T'的权值≤最小生成树T的权值，与T是一棵最小生成树矛盾。因此，与顶点1关联的最小权值边一定包含在一棵生成树中。1ij

T1ij

1ij

T'Prim算法正确性证明（2）假设Prim算法第k步选择的边构成一棵最小生成树的边，证明算法第k+1步选择的边也构成一棵最小生成树的边。假设算法进行了k步，生成树的边为e1,e2,...,ek，这些边的端点构成集合S，由归纳假设存在G的一棵最小生成树T包含这些边。算法第k+1步选择顶点ik+1，则ik+1到S中顶点边权值最小，设此边ek+1=（ik，ik+1）。若ek+1∈T，则算法k+1显然正确。Prim算法正确性证明若T不包含ek+1，将ek+1加T中形成一条回路，这条回路有另外一条连接S与顶点ik+1的边e，令,则T*是一棵生成树，包含e1,e2,...,ek，ek+1，且T*的各边权值之和小于等于T的各边权值之和，说明T*也是一颗最小生成树，算法到k+1步仍然得到最小生成树。证明过程如图所示。权值最小ek+1i1ikS1

V-Sik+1e时间效率分析当使用邻接矩阵存储图时，Prim算法的时间复杂度为O(n2)，其中n是顶点的数量。这是因为Prim算法需要遍历每个顶点，并在每次迭代中找到与当前生成树最近的顶点。当使用邻接表存储图时，Prim算法的时间复杂度为O((n+e)logn)，其中e是边的数量。这是因为Prim算法使用最小堆来选择最小权值的边，每次从堆中取出边的时间复杂度为O(logn)，而最多有n个顶点和e条边。计算机算法设计与分析第5章贪心法5.2.3单源最短路径问题给定一个带权有向图

G=(V,E)，其中每条边的权是一个非负实数。给定图G中的一个顶点v0∈V，称为源点。求源点v0到G中其余各顶点的最短路径长度。这里的长度是指路径上各边权之和。这个问题通常称为单源最短路径问题。5.2.3单源最短路径问题源点终点最短路径路径长度11无

2(1,3,2)7

3(1,3)3

4(1,3,2,4)9

5(1,3,5)55.2.3单源最短路径问题dist[i]表示计算过程中源点到各目标顶点i的当前最短路径长度，dist[i]随着计算过程会不断变化，其初始值为源点到其余顶点有向边的权值，若不存在有向边则用无穷大。path[i]表示在最短路径上顶点i的前一个顶点编号。集合S表示已求出最短路径的顶点的集合。集合T（T=V-S）表示尚未确定最短路径的顶点集合，V是图G中顶点的集合。二维数组edge表示图G的邻接矩阵。贪心策略，Dijkstra算法迪杰斯特拉（Dijkstra）提出了一个按路径长度递增次序产生最短路径的贪心算法，对于有向带权图