算法-贪心算法

第5章贪心算法主要内容5.1贪心算法概述5.2贪心算法的理论基础5.3删数字问题5.4背包问题5.5覆盖问题5.6图的着色问题5.7遍历问题5.8最小生成树5.9哈夫曼编码其他贪心算法：Dijkstra最短路径5.1.1贪心算法找零钱问题，希望用数目最少的硬币找零假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。假设需要找67美分，25+25+10+5+1+1，共6枚。假设提供了数目不限的面值为11美分、5美分及1美分的硬币？找零15美分

11+1+1+1+1，共5枚（贪心算法）

5+5+5，共3枚（非贪心算法）5.1贪心算法概述贪心算法通过一系列的局部选择来得到一个问题的解。所作的每一个选择都是当前状态下“最优”的选择。要依照某种策略。策略“只顾眼前，不管将来”，称之为“贪心策略”。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。5.1.2.贪心算法的基本思想

贪心算法的基本思想是通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足：

(1)可行的：必须满足问题的约束。

(2)局部最优：当前所有可能的选择中最佳的局部选择。

(3)不可取消:

选择一旦做出，在后面的步骤中就无法改变了。贪心算法是通过做一系列的选择来给出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择。这种启发式策略并不总是能产生出最优解。例5.1删除数字问题键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输出应包括所去掉的数字的位置和组成的新的正整数(N不超过100位)。数据结构设计：将输入的高精度数存储为字符串格式。实例(s=3)：n1=“12435863”贪心策略在位数固定的前提下，让高位的数字尽量小其值就较小；删除高位较大的数字；具体地相邻两位比较若高位比低位大则删除高位。n1=“12435863”4比3大删除4“1235863”8比6大删除8“123563”6比3大删除6“12353”再一个实例：n2=“231183”3比1大删除3“21183”2比1大删除2“1183”8比3大删除8“113”由实例1，相邻数字只需要从前向后比较；而从实例2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i+1位进行比较，才能保证结果的正确性。n3=”1234567”s=3由这个实例看出，经过对n3相邻比较一个数字都没有删除，这就要考虑将后三位进行删除；当然还有可能，在相邻比较的过程中删除的位数小于s时，也要进行相似的操作。n4=”120083”s=32比0大删除2“10083”1比0大删除1“0083”8比3大删除8“003”由这个实例子又能看出，当删除掉一些数字后，结果的高位有可能出现数字“0”，直接输出这个数据不合理，要将结果中高位的数字“0”删除掉，再输出。特别地还要考虑若结果串是“0000”时，不能将全部“0”都删除，而要保留一个“0”最后输出。#include"stdio.h"#include"string.h"main(){inti,j,k,m,n,x,a[200];charb[200];gets(b);for(n=0,i=0;b[i]!='\0';i++){n++;a[i]=b[i]-48;}scanf("%d",&k);i=0;m=0;x=0;

while(k>x&&m==0){i=i+1;if(a[i-1]>a[i])/*出现递增,删除递增的首数字*/{printf("%d",a[i-1]);for(j=i-1;j<=n-x-2;j++)a[j]=a[j+1];x=x+1;/*x统计删除数字的个数*/i=0;}/*从头开始查递增区间*/if(i==n-x-1)m=1;}/*已无递增区间,m=1脱离循环*/printf("\n删除后所得最大数:");for(i=1;i<=n-k;i++)/*打印剩下的左边n-k个数字*/printf("%d",a[i-1]);}例5.2数列极差问题

在黑板上写N个正整数排成一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为M=max-min。如： 对三个具体数据3，5，7讨论，可能有以下三种结果：(3*5+1)*7+1=113,(3*7+1)*5+1=111,(5*7+1)*3+1=109结论：先运算小数据得到的是最大值，先运算大数据得到的是最小值。

显然此问题适合用贪婪策略,不过在求最大值时，要先选择较小的数操作。求最小值时，要先选择较大的数操作。这是一道两次运用贪心策略解决的问题。1）不断从现有的数据中，选取最大和最小的两个数，计算后的结果继续参与运算，直到剩余一个数算法结束。2)选取最大和最小的两个数较高效的算法是用二分法完成，这里仅用简单的逐个比较方法来求解。注意到由于找到的两个数将不再参与其后的运算，其中一个用它们的计算结果代替，另一个用当前的最后一个数据覆盖即可。所以不但要选取最大和最小，还必须记录它们的位置，以便将其覆盖。3）求max、min过程必须独立，即求max和min都必须从原始数据开始,否则不能找到真正的max和min。1)由设计2）、3）知，必须用两个数组同时存储初始数据。2)求最大和最小的两个数的函数至少要返回两个数据，方便起见用全局变量实现。

ints1,s2;main(){intj,n,a[100],b[100],max,min;printf("Howmangdata?");scanf("%d",&n);printf("inputthesedata");for(j=1;j<=n;j=j+1){scanf("%d",&a[j]);b[j]=a[j];}min=calculatemin(a,n);max=calculatemax(b,n);printf("max=%d,min=%d,max-min=%d",max,min,max-min);}求一组数据中两个最大值算法：

a[12345678…]

可以假设两个变量s1,s2分别储存这两个值所在数组中的下标，一个最大，一个次大值。数组只有两个元素时：a1>a2,令s1=1,s2=2;否则s1=2,s2=1;

数组再增加一个元素j（下标）时：

if(a[j]>a[s1]){s2=s1;s1=j;}elseif(a[j]>a[s2])s2=j;

max2(inta[],intn){intj;if(a[1]>=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for(j=3;j<=n;j++){if(a[j]>a[s1]){s2=s1;s1=j;}elseif(a[j]>a[s2])s2=j;}}intcalculatemin(inta[],intn){intj;while(n>2){max2(a,n);a[s1]=a[s1]*a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]*a[2]+1);}min2(inta[],intn){intj;if(a[1]<=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for(j=3;j<=n;j++)if(a[j]<a[s1]){s2=s1;s1=j;}elseif(a[j]<a[s2])s2=j;}intcalculatemax(inta[],intn){intj;while(n>2){min2(a,n);a[s1]=a[s1]*a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]*a[2]+1);}贪心算法例子：设计一个算法，把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为1的分数。如：7/8=1/2+1/3+1/24。基本思想：逐步选择分数所包含的最大埃及分数，这些埃及分数之和就是问题的一个解。如：7/8>1/2，

7/8-1/2>1/3，

7/8-1/2-1/3=1/24。过程如下：

1)找最小的n（最大的埃及分数1/n），使分数f>1/n；

2)输出1/n；

3)计算f=f-1/n；

4)若此时的f是埃及分数，输出f,算法结束,否则返回1）。森林里进行一场装背包比赛：参加者：黑熊猴子啄木鸟每个比赛者一个背包，背包的载重量为20公斤。给定N个物品，每个物品有一定的重量和价值。20kg5.3背包问题

森林里进行一场装背包比赛规则：物品可切一部分放入；背包里装的物品的总重量不超过背包的载重量；背包里装的物品的价值最高者获胜。黑熊

黑瞎子掰棒子的策略：价值高的优先放入。物品n=3，背包的载重量C=20各个物品的价值(v1,v2,v3)=(25,24,15)各个物品的重量(w1,w2,w3)=(18,15,10)。物品1物品212/15(25,18)(24*2/15,2)计算器25+24*(2/15)

=

28.2物品3物品212/3猴子耍小聪明策略：重量小的优先放入。物品n=3，背包的载重量C=20各个物品的价值(v1,v2,v3)=(25,24,15)各个物品的重量(w1,w2,w3)=(18,15,10)。计算器15+24*(2/3)

=

31

啄木鸟算盘子策略：单位重量价值高的优先放入。物品n=3，背包的载重量C=20各个物品的价值(v1,v2,v3)=(25,24,15)各个物品的重量(w1,w2,w3)=(18,15,10)单位价值

(v1/w1,v2/w2,v3/w3)=(1.39,1.6,1.5)物品2物品311/2计算器24+15*(1/2)

=

31.5啄木鸟算盘子策略的时间复杂度?第一步:选出单位重量价值最高者装入。

n个中取最大值第二步：删除该物品。第三步:重复1,2步,直至再装入就超出背包的载重量为止。第四步:把最后选择物品的一部分装入背包:

剩余载重量/最后选择物品的重量O(n)O(n2)O(n)啄木鸟算盘子策略能否改进?时间复杂度?第一步:按照单位重量价值递减排序。

n个数排序第二步:按排序顺序依次装入直至再装入就超出背包的载重量为止。第三步:把最后选择物品的一部分装入背包:

剩余载重量/最后选择物品的重量O(nlogn)O(nlogn)O(n)背包问题

该问题就是背包问题：已知：给定n种物品和一个背包。物品i重量是Wi，其价值为Vi，背包容量为C。求解：如何选择装入背包的物品，使得装入背包中物品总价值最大?每个物品xi可以不被装入背包，也可以部分装入背包,0≤xi≤1每个物品的价值和重量值都大于0，总共有n个物品，vi>0，wi>0，1≤i≤n约束条件:背包载重量是C，因此选入背包中物品的总重量不得超过C背包问题的形式化描述问题的求解目标:背包中的物品总价值最大。目标函数: max物品可拆背包问题C程序设计代码如下：for(i=1;i<=n-1;i++)/*对n件物品按单位重量的效益从大到小排序*/for(j=i+1;j<=n;j++)if(p[i]/w[i]<p[j]/w[j]){h=p[i];p[i]=p[j];p[j]=h;h=w[i];w[i]=w[j];w[j]=h;}cw=c;s=0;/*cw为背包还可装的重量*/for(i=1;i<=n;i++){if(w[i]>cw)break;x[i]=1.0;/*若w(i)<=cw,整体装入*/cw=cw-w[i];s=s+p[i];}x[i]=(float)(cw/w[i]);/*若w(i)>cw,装入一部分x(i)*/s=s+p[i]*x[i];printf("装包：");/*输出装包结果*/for(i=1;i<=n;i++)if(x[i]<1)break;elseprintf("\n装入重量为%5.1f的物品.",w[i]);if(x[i]>0&&x[i]<1)printf("\n装入重量为%5.1f的物品百分之%5.1f.",w[i],x[i]*100);printf("\n所得最大效益为：%7.1f",s);

二分图是一个无向图，它的n个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A‘覆盖集合B（或简单地说，A’是一个覆盖）。覆盖A‘的大小即为A’中的顶点数目。当且仅当A‘是覆盖B的子集中最小的时，A’为最小覆盖。

5.4覆盖问题

如下图所示：A={1,2,3,4};B={5,6,7,8,9,10,11};选择A的一个最小覆盖子集A‘，使B中的每个顶点至少与A中一个顶点相连。算法设计如下：先构造邻接矩阵，如图1可以构造如下： 图1 图2计算a各个顶点的度，从中选择度最大的顶点，加入到子集中，如第一次，各个顶点度为4，2，4，2，可以将结点1加入到子集。修改邻接矩阵，将结点1从a集合中去掉，与1所连的边都抹掉。如图2。重复上面过程，直到邻接矩阵值都为0，则找到一组解，否则失败。该算法的时间复杂度取决于数据的存储方式，若使用邻接矩阵，则需花(n2)的时间来寻找图中的边，若用邻接链表，则需(n+e)的时间。故覆盖算法总的复杂性为O(n2)或O(n+e)1、活动安排问题

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。5.5图的着色问题

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的时间[si,fi)：（起始时间si，结束时间fi,且si<fi

）。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。

例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314

由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。

若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。

贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。voidGreedySelector(intn,Types[],Typef[],intA[]){A[1]=1;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=1;j=i;}elseA[i]=0;}}下面给出解活动安排问题的贪心算法GreedySelector:各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列

2、多机调度问题 多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

这个问题到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。

约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。

采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。 按此策略，当时，只要将机器i的[0,ti]时间区间分配给作业i即可，算法只需要O(1)时间。 当时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。

例:设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。

排序后：{4(16),2(14),5(6),6(5),3(4),7(3),1(2),}3、地图的着色（4色）定理：任何平面地图可以使用4种颜色给每个不同的城市着色，而保证相邻的城市着不同的颜色思路：把地图上的每个城市抽象为一个点，并给每个城市编号，，相邻的城市之间用直线连接。据此做出邻接矩阵，若第i个城市与第j个城市相邻，则metro[i][j]=1,否则metro[i][j]=0。算法：按照编号从小到大的顺序检查每个城市，对每个城市从1到4使用4种颜色着色，若当前颜色可用（即不与相邻城市颜色相同），则着色；否则测试下一种颜色。

voidcolor(intmetro[N][N],intr_color[N],intsum)

{

inti,j,k;

for(i=1;i<=sum;i++)/*检查所有城市*/

for(j=1;j<=4;j++)/*对每个城市尝试4种颜色的着色方案*/

{

r_color[i]=j;/*尝试着色*/

for(k=1;k<i;k++)/*检查是否与相邻城市颜色相同*/

if(metro[i][k]==1&&r_color[k]==r_color[i])

break;/*相同则跳出，此时有k<i，则下面条件不成立，继续尝试下一种颜色*/

if(k>=i)/*若不相同，则使用当前颜色，并检查下一个城市*/

break;

}

}#defineN21voidmain()

{

intr_color[N]={0};inti;

intmetro[N][N]={{0},/*邻接矩阵*/

{0,1,1,1,1,1,1},

{0,1,1,1,1},

{0,1,1,1,0,0,1},

{0,1,1,0,1,1},

{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},

{0,1,0,1,0,1,1,1,1,1},

{0,0,0,0,0,0,1,1,1},