程序设计基础12_1_贪心法

1、第第12章章 贪心法贪心法与动态规划与动态规划12.1 12.1 贪贪 心心 法法12.2 12.2 动动 态态 规规 划划问题：问题：假设有面值为假设有面值为5元、元、2元、元、1元、元、5角、角、2角、角、1角的货币，需要角的货币，需要找给顾客找给顾客4元元6角现金，为使付出角现金，为使付出的货币的数量最少，应如何找零？的货币的数量最少，应如何找零？找零问题找零问题解决方法：解决方法：l首先选出首先选出1张面值不超过张面值不超过4元元6角的最大面值的货角的最大面值的货币，即币，即2元；元；l再选出再选出1张面值不超过张面值不超过2元元6角的最大面值的货币，角的最大面值的货币，即即2元；元；

2、l再选出再选出1张面值不超过张面值不超过6角的最大面值的货币，即角的最大面值的货币，即5角；角；l再选出再选出1张面值不超过张面值不超过1角的最大面值的货币，即角的最大面值的货币，即1角；角；总共付出总共付出4张货币。张货币。找零问题找零问题这就是贪心选择！找零问题中的贪心找零问题中的贪心l 在付款问题每一步的贪心选择中，在不超过应付款在付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的货币，而不去考虑金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决在后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定

3、。定：一旦选出了一张货币，就永远选定。l 付款问题的贪心选择策略是尽可能使付出的货币最付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的设计思想。地增加，这正体现了贪心法的设计思想。贪心法的思想贪心法的思想 在实际生活中，经常会遇到类似求一个问题的在实际生活中，经常会遇到类似求一个问题的可行解和最优解的要求，这就是所谓的最优化可行解和最优解的要求，这就是所谓的最优化问题。每个最优化问题都包含一组限制条件和问题。每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解方案

4、一个优化函数，符合限制条件的问题求解方案称为可行解，使优化函数取得最佳值的可行解称为可行解，使优化函数取得最佳值的可行解称为最优解。称为最优解。贪心法的思想贪心法的思想 贪心法是求解这类问题最优解的一种常用算法：贪心法是求解这类问题最优解的一种常用算法： 它从问题的某个初始解出发，采用逐步构造最优解的它从问题的某个初始解出发，采用逐步构造最优解的方法向给定的目标推进。方法向给定的目标推进。 在每个局部阶段，都做出一个看上去最优的决策（即在每个局部阶段，都做出一个看上去最优的决策（即某种意义下的、或某个标准下的局部最优解），并期某种意义下的、或某个标准下的局部最优解），并期望通过每次所做的的局部

5、最优选择产生出一个全局最望通过每次所做的的局部最优选择产生出一个全局最优解。优解。 做出贪心决策的依据称为贪心准则（策略），决策一做出贪心决策的依据称为贪心准则（策略），决策一旦做出，就不可再更改。旦做出，就不可再更改。 贪心与递推的不同之处：贪心推进的每一步不是依据贪心与递推的不同之处：贪心推进的每一步不是依据某一固定的递推式，而是做一个当时看似最佳的贪心某一固定的递推式，而是做一个当时看似最佳的贪心选择（操作），不断地将问题实例归纳为更小的相似选择（操作），不断地将问题实例归纳为更小的相似问题。贪心准则是正确解决贪心问题的关键。问题。贪心准则是正确解决贪心问题的关键。 贪心法的基本思路：贪

6、心法的基本思路：（1 1）建立数学模型来描述问题；）建立数学模型来描述问题；（2 2）把求解的问题分成若干个子问题；）把求解的问题分成若干个子问题；（3 3）对每一子问题求解，得到子问题的局部最优解。）对每一子问题求解，得到子问题的局部最优解。（4 4）把子问题的解局部最优解合成原来解问题的一个解）把子问题的解局部最优解合成原来解问题的一个解。 【例例12.112.1】删数问题删数问题 键盘输入一个高精度的正整数键盘输入一个高精度的正整数n n（ 100100位），去掉其位），去掉其中任意中任意s s个数字后剩下的数字按照原来的左右次序组成个数字后剩下的数字按照原来的左右次序组成一个新的正整数

7、。编程对给定的一个新的正整数。编程对给定的n n与与s s，寻找一种方案，寻找一种方案，使得剩下的数字组成的新数最小。，使得剩下的数字组成的新数最小。 比如：比如：n=178543n=178543，s=4s=4 则输出则输出 13 13 ，表示正整数，表示正整数178543178543，删除，删除4 4位数字后得位数字后得到的最小值是到的最小值是 1313。 （1 1）由于给定的正整数有效位数是）由于给定的正整数有效位数是100100位，位，用一般的整数类型（包括长整数）无法表示，用一般的整数类型（包括长整数）无法表示，可以考虑用字符串来存储正整数。可以考虑用字符串来存储正整数。 （2 2）如

8、何决定哪）如何决定哪s s位数字被删除呢？被删除的位数字被删除呢？被删除的是否是最大的是否是最大的s s个数字呢？为了尽可能逼近目个数字呢？为了尽可能逼近目标，采用贪心法来解决问题，标，采用贪心法来解决问题，选取的贪心策略为：选取的贪心策略为： 把对把对s s个数字的删除，看成是一个逐步实现的过程，个数字的删除，看成是一个逐步实现的过程，每一步删除一个数字，用每一步删除一个数字，用s s步完成对步完成对s s个数字的删除。个数字的删除。 每一步总是选择一个使剩下的数最小的数字完成删每一步总是选择一个使剩下的数最小的数字完成删除，也就是按照从高位到低位的顺序进行搜索，如果除，也就是按照从高位到低

9、位的顺序进行搜索，如果各位数字式递增的，则删除最后一位数字；否则，删各位数字式递增的，则删除最后一位数字；否则，删除第一个递减区间的首位数字。这样选择一位数字并除第一个递减区间的首位数字。这样选择一位数字并删除后，便得到一个新的数字串。删除后，便得到一个新的数字串。 以后每一步回到上一步完成删除之后的数字串的串以后每一步回到上一步完成删除之后的数字串的串首，按照上述规则再删除下一个数字。执行首，按照上述规则再删除下一个数字。执行s s次后，便次后，便删除了删除了s s位数字，剩余的数字串便是问题的解。位数字，剩余的数字串便是问题的解。 例如：例如：n=178543n=178543，s=4s=4

10、时的删除过程为：时的删除过程为： 第一步：第一步：n=17n=1785438543，第一个递减区间为，第一个递减区间为85438543，删，删除其首位数字除其首位数字8 8； 第二步：第二步：n=1n=175437543，第一个递减区间为，第一个递减区间为75437543，删除，删除其首位数字其首位数字7 7； 第三步：第三步：n=1n=1543543，第一个递减区间为，第一个递减区间为543543，删除其，删除其首位数字首位数字5 5； 第四步：第四步：n=1n=14343，第一个递减区间为，第一个递减区间为4343，删除其首位，删除其首位数字数字4 4； 剩余的数字串为：剩余的数字串为：1

11、313，即为所求。，即为所求。#include stdio.h#include stdio.h#include string.h#include string.hint main()int main() int i,s,len;int i,s,len;char a100;char a100;scanf(%s,a);scanf(%s,a);scanf(%d,&s);scanf(%d,&s);while(s0)while(s0) i=0;i=0;len=strlen(a);len=strlen(a);while(ilen &ai=ai+1)while(ilen &a

12、i=ai+1)i+;i+;while(ilen)while(ilen) ai=ai+1;ai=ai+1;i+;i+; s-;s-; printf(%sn,a);printf(%sn,a);return 0;return 0; 【例例12.212.2】 事件序列问题事件序列问题-活动选择问题活动选择问题参考资料：参考资料：http:/ 0# 1# 2# 3# 4# 5# 6# 7# 8# 9# 10#11#发生时刻 1303256410 81515结束时刻 3478910 12 14 15 18 1920 已知已知N=12N=12个事件的发生时刻和结束时刻（见下表，其个事件的发生时刻和结束时刻（

13、见下表，其中事件已经按结束时刻升序排序）。一些在时间上没有中事件已经按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件重叠的事件，可以构成一个事件序列，如事件2 2，8 8和和1010，可以写成序列，可以写成序列22，8 8，1010。事件序列包含的事件。事件序列包含的事件数目，称为事件序列的长度。请编程找出一个最长的事数目，称为事件序列的长度。请编程找出一个最长的事件序列。件序列。各事件在时间上的占用情况012345678910111213141516171819200#1#2#3#4#5#6#7#8#9#10#11#2，8，10序列不是最长的序列0，1，7，10

14、更长一些 如何选择事件，可以保证得到最长的事件序列呢？ 用用beginibegini表示事件表示事件i i的发生时刻，用的发生时刻，用endiendi表示事件表示事件i i的的结束时刻。结束时刻。 如果两个事件如果两个事件a a，b b（a ab b）在时间上没有重叠，那么有）在时间上没有重叠，那么有 endabeginbendabeginb； 如果满足这个条件，则两个事件在时间上一定没有重叠如果满足这个条件，则两个事件在时间上一定没有重叠，这是一个，这是一个充分必要充分必要条件。条件。 原题的要求其实就是找到一个最长的序列原题的要求其实就是找到一个最长的序列a a1 1a a2 2a an

15、n，满足：，满足： begina begina1 1 endaenda1 1beginabegina2 2 endaenda2 2 beginabeginan nendaendan n 本题目的贪心策略：即为了得到当前情况下最优的一本题目的贪心策略：即为了得到当前情况下最优的一个结果，可以在当前可选的事件中选取编号最小的那个结果，可以在当前可选的事件中选取编号最小的那个进入序列，也就是选取最早结束的那个事件进入序个进入序列，也就是选取最早结束的那个事件进入序列。即：列。即： 第一个要选取的事件是最早结束的事件；第一个要选取的事件是最早结束的事件； 下一个要选取的事件，必须是上一个选取的事件结束

16、下一个要选取的事件，必须是上一个选取的事件结束之后开始的事件中最早结束的事件；之后开始的事件中最早结束的事件； 在程序中设置一个在程序中设置一个selectiselecti标记数组，表示事件标记数组，表示事件i i是否是否要选入序列，选入时值为要选入序列，选入时值为1 1，否则值为，否则值为0 0。 #include stdio.h#include stdio.h#define N 12#define N 12void outputresult(int select,int n)void outputresult(int select,int n) int i;int i;printf(0);

17、printf(0);for(i=1;in;i+)for(i=1;in;i+)if(selecti=1)if(selecti=1)printf(,%d,i);printf(,%d,i);printf(n);printf(n); int main()int main() char beginN=1,3,0,3,2,5,6,4,10,8,15,15;char beginN=1,3,0,3,2,5,6,4,10,8,15,15;int endN=3,4,7,8,9,10,12,14,15,18,19,20;int endN=3,4,7,8,9,10,12,14,15,18,19,20;int sele

18、ctN=0;int selectN=0;int i=0;int i=0;int timestart=0;int timestart=0;while(iN)while(i=timestart)if (begini=timestart) selecti=1;selecti=1;timestart=endi;timestart=endi; i+;i+; outputresult(select,N);outputresult(select,N);return 0;return 0; 【例【例12.312.3】 区间覆盖问题区间覆盖问题【例例12.312.3】 区间覆盖问题区间覆盖问题例如例如M=5M=

19、5，整数，整数1 1、3 3、4 4、8 8和和1111表示区间表示区间，要求所用，要求所用线段不超过线段不超过N=3N=3条条。118431f1：f2：f3：f4：01234567891011M=56788Totallength方案方案f4正是这个任务的答案正是这个任务的答案 用用i i来表示来表示x x坐标轴上坐标为坐标轴上坐标为i-1i-1，i i的的长度为长度为1 1的区间的区间，并给出，并给出M(1M200)M(1M200)个不同的整数，表示个不同的整数，表示MM个这样的区间个这样的区间。现在要求。现在要求画几画几条线段覆盖住所有的区间条线段覆盖住所有的区间，条件是：每条线段可以任意

20、长，但是要求，条件是：每条线段可以任意长，但是要求所画所画线段的长度之和最小线段的长度之和最小，并且线段的，并且线段的数目不超过数目不超过NN(1N50)(1N50)。设置一个整型数组设置一个整型数组positionMpositionM来表示所有的区间，假设来表示所有的区间，假设positionMpositionM已经按从小到大的顺序排好。已经按从小到大的顺序排好。如果如果NMNM，那么用，那么用MM条长度为条长度为1 1的线段可以覆盖住所有的的线段可以覆盖住所有的区间，所求的线段总长为区间，所求的线段总长为MM。如果如果NNMM，显然，显然MM1,1,可以按照如下的贪心策略来解决：可以按照如

21、下的贪心策略来解决： 0 01 12 23 34 4134811position11843101234567891011M=5如果如果N=1N=1，即要用一条线段覆盖住所有区间，即要用一条线段覆盖住所有区间，很显然所需线段总长即为很显然所需线段总长即为positionM-1-positionM-1-position0+1position0+1。图图12.3 N=1条线段覆盖所有条线段覆盖所有区区间间position012M-1N=1 如果如果N=2N=2，即要用两条线段覆盖住所有区间，相当于，即要用两条线段覆盖住所有区间，相当于把把N=1N=1中的线段分为两部分，各覆盖住左边与右边的区中的线段

22、分为两部分，各覆盖住左边与右边的区间。间。 如果线段在如果线段在MM个区间中不相邻的区间之间断开（如在个区间中不相邻的区间之间断开（如在position0position0与与position1position1之间），左右两段线段的端之间），左右两段线段的端点可调整到坐标点可调整到坐标position0+1position0+1与与position1position1处，这处，这样总长度小于断开之前。样总长度小于断开之前。position012M-1N=2N=1线段长度减少线段长度减少:position1-(position0+1)。图中两条线段长度之和，比图中两条线段长度之和，比 原来一条

23、线段长度减少了原来一条线段长度减少了position1position1和和position0+1position0+1之间的距离，即：之间的距离，即： position1-position0-1 position1-position0-1。题目要求最小线段总长，可以找间隔最大的两个相邻区间，在它题目要求最小线段总长，可以找间隔最大的两个相邻区间，在它们之间断开就可以了。这一过程相当于找们之间断开就可以了。这一过程相当于找 distancei=positioni-positioni-1-1 distancei=positioni-positioni-1-1 (1 (1i iM)M)的最大值。的

24、最大值。 0 01 12 23 34 4134811position11843101234567891011M=51 10 03 32 2distance如果如果N=3N=3，相当于在，相当于在N=2N=2的方案下，将某条的方案下，将某条线段断成两截，并作可能的端点调整。线段断成两截，并作可能的端点调整。显然，为了得到当前情况下最小的总长度，显然，为了得到当前情况下最小的总长度，同样应该在间隔最大的两个相邻区间之间断同样应该在间隔最大的两个相邻区间之间断开。开。如果原来的方案是如果原来的方案是N=2N=2时总长最小的方案，时总长最小的方案，这一操作可以得到这一操作可以得到N=3N=3时总长最小

25、的方案。时总长最小的方案。当当N=kN=k（k k1 1）时依此类推，只需在）时依此类推，只需在N=k-1N=k-1时最小总长的覆盖方案下，找到被同一条线时最小总长的覆盖方案下，找到被同一条线段覆盖的间隔最大的两个相邻区间，段覆盖的间隔最大的两个相邻区间，“贪心贪心”地从间隔处断开并适当调整两边线段的端地从间隔处断开并适当调整两边线段的端点，就可以得到这是总长最小的方案。点，就可以得到这是总长最小的方案。#include #include #define N 200 / #define N 200 / 区间数目的上限区间数目的上限void sort1(int value,int n) / vo

26、id sort1(int value,int n) / 排序函数（非递增）排序函数（非递增） int i,j,t;int i,j,t;for(i=0;in-1;i+)for(i=0;in-1;i+)for(j=0;jn-1-i;j+)for(j=0;jn-1-i;j+)if(valuejvaluej+1)if(valuejvaluej+1) t=valuej;t=valuej;valuej=valuej+1;valuej=valuej+1;valuej+1=t;valuej+1=t; int main()int main() int m,i,n; / mint m,i,n; / m是要覆盖的区

27、间数，是要覆盖的区间数，n n是可用于覆盖的线段数是可用于覆盖的线段数int positionN; / int positionN; / 各个要覆盖的区间各个要覆盖的区间int distanceN-1; / int distanceN-1; / 存放相邻区间的距离存放相邻区间的距离printf(printf(请输入要覆盖的区间数请输入要覆盖的区间数m= );m= );scanf(%d,&m); / scanf(%d,&m); / 输入要覆盖的区间数输入要覆盖的区间数printf(printf(请输入请输入 %d %d 个要覆盖的区间：个要覆盖的区间： ,m);,m);for(i

28、=0;im;i+)for(i=0;im;i+)scanf(%d,&positioni); / scanf(%d,&positioni); / 输入输入mm个区间个区间sort1(position,m); / msort1(position,m); / m个区间降序排列个区间降序排列for(i=0;im-1;i+)for(i=0;i=m)if(n=m) printf(printf(最小的线段总长为：最小的线段总长为：%dn,m);%dn,m);return 0;return 0; int nline=1; / int nline=1; / 当前情况下所用线段总数当前情况下所用线段

29、总数int totallength=position0-positionm-1+1;int totallength=position0-positionm-1+1; / / 当前情况下所用线段总长当前情况下所用线段总长int devide=0; / int devide=0; / 当前最大的未断开的区间距离当前最大的未断开的区间距离while(nlinen)& / while(nline0) / (distancedevide0) / 还有不相邻的区间还有不相邻的区间 nline+; / nline+; / 再用一条线段再用一条线段totallength-=distancedevide

30、; / totallength-=distancedevide; / 总长减少总长减少devide+; / devide+; / 覆盖该区间的线段断开，指向下一最大间隔覆盖该区间的线段断开，指向下一最大间隔 printf(printf(最小线段总长为：最小线段总长为：%dn,totallength);%dn,totallength);return 0;return 0; 118431n=101234567891011M=56811Totallengthn=2n=312.1.3贪心法解题的一般步骤 上面三个任务所用的算法由一个共同点，就是在求最上面三个任务所用的算法由一个共同点，就是在求最优解的过程中，每一步都采用一种局部最优的策略，优解的过程中，每一步都采用一种局部最优的策略，把问