第6章贪心算法.ppt

《第6章贪心算法.ppt》由会员分享，可在线阅读，更多相关《第6章贪心算法.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 贪心算法贪心算法 若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为步而推导出问题，这种策略称为贪心法贪心法。下面我们看一些简单例题。下面我们看一些简单例题。【例【例1】在在N行行M列的正整数矩阵中，要求从每行中选出列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共个数，使得选出的总共N个个数的和最大。数的和最大。【算法分析】【算法分析】 要使

2、总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法我们设计出如下算法:读入读入N, M,矩阵数据；矩阵数据；Total = 0;for (int l= 1; l=0) /将第i种商品全部装入卡车 else 将(m+wi) 重量的物品i装入卡车; i=i+1; /选择下一种商品while (m0&inr; memset(s,0,sizeof(s); /初始化 j=0; minx=0; for (i=1;i=n;+i) /用贪心法求解 j+; if (j=r+1) j=1; /前前r个人为一组，

3、第个人为一组，第r+1个人回到第一个水龙个人回到第一个水龙 sj+=ai; /加上等待时间加上等待时间 minx+=sj; cout从取3张牌放到 （9 11 10 10）- 从取1张牌放到（10 10 10 10）。【输入格式】 N（N 堆纸牌，1 = N = 100） A1 A2 An （N 堆纸牌，每堆纸牌初始数，l= Ai n;ave=0;step=0; for (i=1;iai; ave+=ai; /读入各堆牌张数，求总张数读入各堆牌张数，求总张数ave ave/=n; /求牌的平均张数求牌的平均张数avefor (i=1;i=n;+i) ai-=ave; /每堆牌的张数减去平均数每

4、堆牌的张数减去平均数i=1;j=n;while (ai=0&i1) -j; /过滤右边的过滤右边的0while (ij) ai+1+=ai; /将第将第i堆牌移到第堆牌移到第i+1堆中去堆中去ai=0; /第第i堆牌移走后变为堆牌移走后变为0+step; /移牌步数计数移牌步数计数 +i; /对下一堆牌进行循环操作对下一堆牌进行循环操作while (ai=0&ij) +i; /过滤移牌过程中产生的过滤移牌过程中产生的0 coutstependl; 点评：基本题，本题有点评：基本题，本题有3点比较关键：一是善于将每堆牌数减去平均数，简化了点比较关键：一是善于将每堆牌数减去平均数，简化了问题；二是

5、要过滤掉问题；二是要过滤掉0（不是所有的（不是所有的0，如，如-2，3，0，-1中的中的0是不能过滤的）；三是是不能过滤的）；三是负数张牌也可以移动，这是关键中的关键。负数张牌也可以移动，这是关键中的关键。【例【例5】删数问题（】删数问题（NOI94）输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。 输出新的正整数。（N不超过240位）输入数据均不需判错。【输入】 n s【输出】 最后剩下的最小数。【样例输入】 175438 4【样例输出】 13【算法分析】 由于正整数n的有效数位为240位

6、，所以很自然地采用字符串类型存贮n。那么如何决定哪s位被删除呢？是不是最大的s个数字呢？显然不是，大家很容易举出一些反例。为了尽可能逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符，这样删一位便形成了一个新数字串。然后回到串首，按上述规则再删下一个数字。重复以上过程s次为止，剩下的数字串便是问题的解了。例如：n=175438 s=4 删数的过程如下： n=175438 /删掉7 15438 /删掉5 1438 /删掉4 138 /删掉8 13 /解为13 这样，删数问题就与如

7、何寻找递减区间首字符这样一个简单的问题对应起来。不过还要注意一个细节性的问题，就是可能会出现字符串串首有若干0的情况，甚至整个字符串都是0的情况。按以上贪心策略编制的程序框架如下 输入n，s； for (i=1;i=s;+i) /一共要删除s个字符 for ( j=0;jnj+1 ) /找到第一个符合条件的 for ( k=j;k导弹导弹i的高度的高度；lp导弹导弹i的高度的高度)（ijk）。这样可使得）。这样可使得一套系统拦截的导弹数尽可能增多。一套系统拦截的导弹数尽可能增多。依次类推，直至分析了依次类推，直至分析了n枚导弹的高度为止。此时得出的枚导弹的高度为止。此时得出的k便为应配备的最少

8、系统数。便为应配备的最少系统数。参考程序主要框架如下：参考程序主要框架如下：k=1;lk=导弹导弹1的高度的高度; for (i=2;i=n;+i) p=0;for (j=1;j=导弹导弹i的高度的高度) if (p=0) p=j; else if (ljlp) p=j; /贪心贪心 if (p=0) +k;lk=导弹导弹i的高度的高度; /增加一套新系统增加一套新系统 else lp=导弹导弹i的高度的高度; /贪心贪心,更新第更新第p套系统的最低高度套系统的最低高度 输出应配备的最少系统数输出应配备的最少系统数K。 【例7】活动选择 学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂

9、，在同一时间，礼堂只能被一个活动使。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。 现在给出n个活动使用礼堂的起始时间begini和结束时间endi(begini endi)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。 【输入】 第一行一个整数n(n=1000)； 接下来的n行，每行两个整数，第一个begini，第二个是endi(begini endi =32767)【输出】 输出最多能安排的活动个数。【样例输入】113 51 412 148 120 68 116 105 73 85 92 13【样例输出】 4 【算法分析】 算法模型：

10、给n个开区间（begini,endi）, 选择尽量多的区间, 使得两两不交。 做法: 首先按照end1=end2=endn的顺序排序,依次考虑各个活动, 如果没有和已经选择的活动冲突, 就选; 否则就不选。 正确性: 如果不选end1, 假设第一个选择的是endi,则如果endi和end1不交叉则多选一个end1更划算; 如果交叉则把endi换成end1不影响后续选择。 【参考程序】#includeusing namespace std;int n,begin1001,end1001;void init() cinn; for(int i=1;ibeginiendi;void qsort(in

11、t x,int y) int i,j,mid,t; i=x;j=y;mid=end(x+y)/2; while(i=j) while(endimid) -j; if(i=j) t=endj;endj=endi;endi=t; t=beginj;beginj=begini;begini=t; +i;j; if(xj) qsort(x,j); if(iy) qsort(i,y); void solve() int ans=0; for(int i=1,t=-1;i=t) +ans;t=endi;/如果当前活动与之前最后结束的活动不冲突， 就接受当前活动。 coutansendl;int main(

12、) init(); qsort(1,n); solve(); return 0; 【例8】整数区间 请编程完成以下任务： 1.从文件中读取闭区间的个数及它们的描述； 2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。 【输入】 首行包括区间的数目n,1=n=10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0=a=b=10000,它们是某一个区间的开始值和结束值。【输出】 第一行集合元素的个数,对于每一个区间都至少有一个整数属于该区间,且集合所包含元素数目最少。【样例输入】 43 62 40 24 7【样例输出】2 【算法分析

13、】 算法模型：给n个闭区间ai,bi, 在数轴上选尽量少的点,使每个区间内至少有一个点。 算法：首先按b1=b2=.=bn排序。每次标记当前区间的右端点x，并右移当前区间指针，直到当前区间不包含x,再重复上述操作。 如下图，如果选灰色点，移动到黑色点更优。 【参考程序】#includeusing namespace std;int a10001,b10001,sum=0,n,m;void qsort(int x,int y) /多关键字快排 int i,j,mid1,mid2,t; i=x;j=y;mid1=b(x+y)/2;mid2=a(x+y)/2; while(i=j) while(bi

14、mid1|(bi=mid1)&(aimid1|(bj=mid1)&(ajmid2) -j; if(i=j) t=bj;bj=bi;bi=t; t=aj;aj=ai;ai=t; +i; -j; if(xj) qsort(x,j); if(in; for(int i=1;iaibi; qsort(1,n); for(int i=1,x=-1;i=ai) continue; /如果当前区间包含标记点，就跳过。 +sum; x=bi; /更新标记点。 coutsum从取3张牌放到 （9 11 10 10）- 从取1张牌放到（10 10 10 10）。【输入格式】【输入格式】N（N 堆纸牌，1 = N

15、= 100）A1 A2 An （N 堆纸牌，每堆纸牌初始数，l= Ai =10000）【输出格式】【输出格式】所有堆均达到相等时的最少移动次数。【样例输入】【样例输入】(Playcard.in)49 8 17 6 【样例输出【样例输出】(Playcard.out)33、拦截导弹问题（、拦截导弹问题（NOIP1999）【问题描述】【问题描述】某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。输入

16、导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。【输入格式】【输入格式】 n颗依次飞来的高度（1n1000）.【输出格式】【输出格式】 要拦截所有导弹最小配备的系统数k。【输入样例】【输入样例】missile.in 389 207 155 300 299 170 158 65【输出样例】【输出样例】missile.out 24、排队接水、排队接水(water.pas)【问题描述】【问题描述】 有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。【输入格式】

17、【输入格式】 输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，Tn，每个数据之间有1个空格。【输出格式】【输出格式】 输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。【输入输出样例】【输入输出样例】water.in103 2 7 8 1 4 9 6 10 556 12 1 99 1000 234 33 55 99 812water.out532.005、最大整数（、最大整数（Noip1998连接多位数）连接多位数）【问题描述】【问题描述】 设有n个正整数（n20），将它们联接成一

18、排，组成一个最大的多位整数。 例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213 又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613【输入格式】【输入格式】n n个数【输出格式】【输出格式】联接成的多位数【输入样例】【输入样例】maxnum.in313 312 343【输出样例】【输出样例】maxnum.out 343312136、纪念品分组、纪念品分组(NOIP2007)【题目描述】【题目描述】 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，

19、但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。【输入格式】【输入格式】 输入文件group.in包含n+2行： 第1行包括一个整数w，为每组纪念品价格之和的上限。 第2行为一个整数n，表示购来的纪念品的总件数。 第3n+2行每行包含一个正整数pi (5 = pi = w)，表示所对应纪念品的价格。【输出格式】【输出格式】 输出文件group.out仅一行，包含一个整数，即最少的分组数目。【输入输出样例】【输入输出样例】【

20、限制】【限制】 50%的数据满足：1 = n = 15 100%的数据满足：1 = n = 30000, 80 = w = 200group.ingroup.in1009902020305060708090group.outgroup.out67、合并果子、合并果子(Noip2004)【问题描述】【问题描述】 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并

21、所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。【输入文件】【输入文件】 输入文件fruit.in包括两行，第一行是一个整数n（1 = n = 10000），表示果子的种类数。

22、第二行包含n个整数，用空格分隔，第i个整数ai（1 = ai = 20000）是第i种果子的数目。【输出文件】【输出文件】 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。【样例输入】【样例输入】31 2 9【样例输出】【样例输出】15【数据规模】【数据规模】对于30%的数据，保证有n = 1000；对于50%的数据，保证有n = 5000；对于全部的数据，保证有n = 10000。8、美元汇率（、美元汇率（DOLLARS.PAS）【问题描述】【问题描述】 在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或

23、卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。【输入格式】【输入格式】 输入文件的第一行是一个自然数N，1N100，表示戴维学习汇率的天数。接下来的N行中每行是一个自然数A，1A1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。【输出格式】【输出格式】 输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。 注意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。【输入样例】【输入样例】DOLLARS.

24、IN5400300500300250【输出样例】【输出样例】DOLLARS.OUT266.66样例解释样例解释 (无需输出无需输出)Day 1 . changing 100.0000 美元= 400.0000 马克Day 2 . changing 400.0000 马克= 133.3333 美元Day 3 . changing 133.3333 美元= 666.6666 马克Day 5 . changing 666.6666 马克= 266.6666 美元9、零件分组（、零件分组（stick.pas）【问题描述问题描述】 某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若ij，则Li=Lj，Wi=Wj）的序列。请问至少要分成几组?【输入格式】【输入格式】 第一行为一个整数N（N=1000），表示零件的个数。第二行有N对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过10000。【输出格式】【输出格式】 仅一行，即最少分成的组数。【输入样例】【输入样例】STICK.IN58 4 3 8 2 3 9 7 3 5【输出样例】【输出样例】STICK.OUT2