方案3为175.7。这里只有第3种策略得到的才是符合要求的最优解。 15.2贪心法实例 15.2.1删数问题 【例15.1】删数问题。 键盘输入一个高精度的正整数n(≤100位)，去掉其中任意s个数字后剩下的数字按 照原来的左右次序组成一个新的正整数。编程对给定的与s,寻找一种方案，使得剩下 的数字组成的新数最小。 比如：n=178543,s=4 则输出13，表示正整数178543，删除4位数字后得到的最小值是13。 分析： (1)由于给定的正整数有效位数是100位，用一般的整数类型（包括长整数）无法表 示，可以考虑用字符串来存储正整数。 (2)如何决定哪s位数字被删除呢？被删除的是否是最大的s个数字呢？为了尽可能 逼近目标，我们采用贪心法来解决问题，选取的贪心策略为： ①把对s个数字的删除，看成是一个逐步实现的过程，每一步删除一个数字，用s步 完成对s个数字的删除。 ②每一步总是选择一个使剩下的数最小的数字完成删除，也就是按照从高位到低位 的顺序进行搜索，如果各位数字是递增的，则刷除最后一位数字：否则，删除第一个递减 区间的首位数字。这样选择一位数字并删除后，便得到一个新的数字串 ③以后每一步回到上一步完成删除之后的数字串的串首，按照上述规则再别除下一 个数字。执行s次后，便删除了s位数字，剩余的数字串便是问题的解。 例如：n=178543,s-4时的删除过程为： 第一步：n=178543,第一个递减区间为8543，删除其首位数字8。 第二步：=17543，第一个递减区间为7543，删除其首位数字7。 第三步：n=1543,第一个递减区间为543，删除其首位数字5 第四步：=143，第一个递减区间为43，别除其首位数字4。 剩余的数字串为：13，即为所求。该问题求解的具体贪心策略如表15-6所示。 表15-6删数问题的贪心策略 步骤当前数字串第一个递减区间递减区间首位数字剩余数字串当前解集合 1 178543 8543 17543 {8 2 17543 7543 7 1543 871 1543 543 143 8.7.51 143 43 13 8.7.5.4} 根据上述思路，可以得到如下的程序： 6
6 方案 3 为 175.7。这里只有第 3 种策略得到的才是符合要求的最优解。 15.2 贪心法实例 15.2.1 删数问题 【例 15.1】 删数问题。 键盘输入一个高精度的正整数 n（≤100 位），去掉其中任意 s 个数字后剩下的数字按 照原来的左右次序组成一个新的正整数。编程对给定的 n 与 s，寻找一种方案，使得剩下 的数字组成的新数最小。 比如：n=178543，s=4 则输出 13，表示正整数 178543，删除 4 位数字后得到的最小值是 13。 分析： （1）由于给定的正整数有效位数是 100 位，用一般的整数类型（包括长整数）无法表 示，可以考虑用字符串来存储正整数。 （2）如何决定哪 s 位数字被删除呢？被删除的是否是最大的 s 个数字呢？为了尽可能 逼近目标，我们采用贪心法来解决问题，选取的贪心策略为： ① 把对 s 个数字的删除，看成是一个逐步实现的过程，每一步删除一个数字，用 s 步 完成对 s 个数字的删除。 ② 每一步总是选择一个使剩下的数最小的数字完成删除，也就是按照从高位到低位 的顺序进行搜索，如果各位数字是递增的，则删除最后一位数字；否则，删除第一个递减 区间的首位数字。这样选择一位数字并删除后，便得到一个新的数字串。 ③ 以后每一步回到上一步完成删除之后的数字串的串首，按照上述规则再删除下一 个数字。执行 s 次后，便删除了 s 位数字，剩余的数字串便是问题的解。 例如：n=178543，s=4 时的删除过程为： 第一步：n=178543，第一个递减区间为 8543，删除其首位数字 8。 第二步：n=17543，第一个递减区间为 7543，删除其首位数字 7。 第三步：n=1543，第一个递减区间为 543，删除其首位数字 5。 第四步：n=143，第一个递减区间为 43，删除其首位数字 4。 剩余的数字串为：13，即为所求。该问题求解的具体贪心策略如表 15-6 所示。 表 15-6 删数问题的贪心策略 步骤 当前数字串 第一个递减区间 递减区间首位数字 剩余数字串 当前解集合 1 178543 8543 8 17543 {8} 2 17543 7543 7 1543 {8,7} 3 1543 543 5 143 {8,7,5} 4 143 43 4 13 {8,7,5,4} 根据上述思路，可以得到如下的程序：
#include "stdio.h" #include "string.h" int main() int i,s,len char a[100] scanf ("&s",a); scanf ("d",&s) wthile(s>0) =0: =strlen(a) while(i<len s6a[i]<-a[i+i]) 1++ while(i<len) a[i]=a[i+1]: 1++: 1 printf("8s\n",a) return 0 以上程序在运行期间，有时会遇上一点小小的问题，即删除过程可能会使原来包含0 的数字串变成以若干个0开始的序列，比如80056，在第一次删除8之后，会变成0056， 高位的0是无效的，请读者对上述程序做一点改进，当遇到数字串首位是0的情况时，把 高位的数字0去掉。 15.2.2活动选择问题 【例15.2】事件序列问题一一活动选择问题。 己知N=12个事件的发生时刻和结束时刻（见表15-7，其中事件已经按结束时刻升序 排序)。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件2、8和10，可以 写成序列{2,8,10；。事件序列包含的事件数目，称为事件序列的长度。请编程找出一个 最长的事件序列。 表15-7事件序列时刻表 事件1编号 0#1#2#34#5#67#8#910#11 发生时 1303256 4108 1515 结束时刻 3478910121415181920 分析： 7
7 #include "stdio.h" #include "string.h" int main() { int i,s,len; char a[100]; scanf("%s",a); scanf("%d",&s); while(s>0) { i=0; len=strlen(a); while(i<len &&a[i]<=a[i+1]) i++; while(i<len) { a[i]=a[i+1]; i++; } s-; } printf("%s\n",a); return 0; } 以上程序在运行期间，有时会遇上一点小小的问题，即删除过程可能会使原来包含 0 的数字串变成以若干个 0 开始的序列，比如 80056，在第一次删除 8 之后，会变成 0056， 高位的 0 是无效的，请读者对上述程序做一点改进，当遇到数字串首位是 0 的情况时，把 高位的数字 0 去掉。 15.2.2 活动选择问题 【例 15.2】 事件序列问题——活动选择问题。 已知 N=12 个事件的发生时刻和结束时刻（见表 15-7，其中事件已经按结束时刻升序 排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件 2、8 和 10，可以 写成序列{2，8，10}。事件序列包含的事件数目，称为事件序列的长度。请编程找出一个 最长的事件序列。 表 15-7 事件序列时刻表 事件 i 编号 0# 1# 2# 3# 4# 5# 6# 7# 8# 9# 10# 11# 发生时刻 1 3 0 3 2 5 6 4 10 8 15 15 结束时刻 3 4 7 8 9 10 12 14 15 18 19 20 分析：
根据各事件的发生时刻和结束时刻画出图来，重叠情况就一目了然，如图15.1所示。 从图15.1上可以很清楚的看出哪些事件在时间上没有重叠，从而找到一些事件序列， 例如2,8,10；。但这个序列不是最长的，序列0,1,7,10；就更长一些。应该如何选择 事件，可以保证得到最长的事件序列呢？ 为了叙述方便，用begin的表示事件i的发生时刻，用cnd回表示事件i的结束时刻。 下面对事件在时间上不重叠的条件进行分析。 从图15.1很容易看出，如果两个事件a、b(a<b)在时间上没有重叠，那么有enda≤ begin[b]:如果满足这个条件，则两个事件在时间上一定没有重叠，这是一个充分必要 条件。 对于3个事件a、b、c(a<b<c),如果a和b,b和c在时间上都没有重叠，则有： end[a]sbegin[b],end[b]sbegin[e] 由于每一件事件的开始时刻一定小于结束时刻，则begin)<end回，则有： begin[a]<end[a]<begin[b]<end[b]sbegin[c]<end[c] 这个条件说明a和c在时间上也没有重叠。反之，如果3个事件a、b、c满足这个条 件，则它们在时间上没有重叠。 ● ●0并 ●一●1# ●2# ●3 5# ● ●6 ●7 ●8 ● ●9啡 ◆10# 1 ● LL上LLLL⊥⊥」 01234567891011121314151617181920 15.1各事件在时间上的占用情况图 依此类推，原题的要求其实就是找到一个最长的序列a1<a<<aa,满足： begin[a]<end[a]<begin[az]<end[az]<begin[an]<end[ao] 如果事件a、b、c满足：cndb≤begin[c],即b与c在时间上不重叠：且 a<b 则根据题意有： end[a]<end[b] 8
8 根据各事件的发生时刻和结束时刻画出图来，重叠情况就一目了然，如图 15.1 所示。 从图 15.1 上可以很清楚的看出哪些事件在时间上没有重叠，从而找到一些事件序列， 例如{2，8，10}。但这个序列不是最长的，序列{0，1，7，10}就更长一些。应该如何选择 事件，可以保证得到最长的事件序列呢？ 为了叙述方便，用 begin[i]表示事件 i 的发生时刻，用 end[i]表示事件 i 的结束时刻。 下面对事件在时间上不重叠的条件进行分析。 从图 15.1 很容易看出，如果两个事件 a、b（a<b）在时间上没有重叠，那么有 end[a]≤ begin[b]；如果满足这个条件，则两个事件在时间上一定没有重叠，这是一个充分必要 条件。 对于 3 个事件 a、b、c（a<b<c），如果 a 和 b，b 和 c 在时间上都没有重叠，则有： end[a] ≤begin[b],end[b] ≤begin[c] 由于每一件事件的开始时刻一定小于结束时刻，则 begin[i] <end[i]，则有： begin[a] <end[a]≤begin[b] <end[b]≤begin[c] <end[c] 这个条件说明 a 和 c 在时间上也没有重叠。反之，如果 3 个事件 a、b、c 满足这个条 件，则它们在时间上没有重叠。 0 1 2 3 4 5 6 7 3 8 9 10 11 12 13 14 15 16 17 18 19 20 0# 1# 2# 3# 4# 5# 6# 7# 8# 9# 11# 10# 图 15.1 各事件在时间上的占用情况图 依此类推，原题的要求其实就是找到一个最长的序列 a1<a2<.<an，满足： begin[a1] <end[a1]≤begin[a2] <end[a2]≤.≤begin[an]<end[an] 如果事件 a、b、c 满足：end[b]≤begin[c]，即 b 与 c 在时间上不重叠；且 a<b 则根据题意有： end[a]≤end[b]
因此，endfa]sbegin[,即a与c在时间上也不重叠。可以推知，如果在可能的事件 a1<a<<an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1的最长序列。 这个结论给出了本题目所采用的贪心策略，即为了得到当前情况下最优的一个结果， 可以在当前可选的事件中选取编号最小的那个进入序列，也就是选取最早结束的那个事件 进入序列。具体来讲就是： ①第一个要选取的事件是最早结束的事件。 ②下一个要选取的事件，必须是上一个选取的事件结束之后开始的事件中最早结束 的事件。 表15-8事件序列问题的贪心策略 步 当前事件开始 t时刻之后开始 F中最早结e事件的 当前解集合 的最早时刻1 的事件集合F 束的事件e 结束时刻 0.11里 O# 04 2 3 1#、3#、5#11# 4 0点1#} 5#、11# 10 {01#5#) 10 8#、10#、11由 8别 15 0,1#,5#,8) 5 15 10#、11# 10# 190m,1#,5#.8游，10} 根据上述思路，在程序中设置一个select[标记数组，表示事件i是否要选入序列，选 入时值为1，否则值为0。可以得到如下的程序： #include "stdio.h" #define N 12 void outputresult(int select[],int n) int i printf("(0") for(i=1;i<n;i++) if(select[i]==1) printf(",8d",i); printf(")\n"); int main() char begin[w]-{1,3,0,3,2,5,6,4,10,8,15,15j: 1 nt end[N]={3,4,7,8,9,10,12,14,15,18,19,20} int select[N]={0); ；n+=0: int timestart-0; while(i<N) if (begin(i]>=timestart) 9
9 因此，end[a]≤begin[c]，即 a 与 c 在时间上也不重叠。可以推知，如果在可能的事件 a1<a2<.<an中选取在时间上不重叠的最长序列，那么一定存在一个包含 a1的最长序列。 这个结论给出了本题目所采用的贪心策略，即为了得到当前情况下最优的一个结果， 可以在当前可选的事件中选取编号最小的那个进入序列，也就是选取最早结束的那个事件 进入序列。具体来讲就是： ① 第一个要选取的事件是最早结束的事件。 ② 下一个要选取的事件，必须是上一个选取的事件结束之后开始的事件中最早结束 的事件。 表 15-8 事件序列问题的贪心策略 步 骤 当前事件开始 的最早时刻 t t 时刻之后开始 的事件集合 F F 中最早结 束的事件 e e 事件的 结束时刻 当前解集合 1 0 0#~11# 0# 3 {0#} 2 3 1#、3#、5#~11# 1# 4 {0#,1#} 3 4 5#~11# 5# 10 {0#,1#,5#} 4 10 8#、10#、11# 8# 15 {0#,1#,5#,8#} 5 15 10#、11# 10# 19 {0#,1#,5#,8#,10#} 根据上述思路，在程序中设置一个 select[i]标记数组，表示事件 i 是否要选入序列，选 入时值为 1，否则值为 0。可以得到如下的程序： #include "stdio.h" #define N 12 void outputresult(int select[],int n) { int i; printf("{0"); for(i=1;i<n;i++) if(select[i]==1) printf(",%d",i); printf("}\n"); } int main() { char begin[N]={1,3,0,3,2,5,6,4,10,8,15,15}; int end[N]={3,4,7,8,9,10,12,14,15,18,19,20}; int select[N]={0}; int i=0; int timestart=0; while(i<N) { if (begin[i]>=timestart) {
select【i】-1: timestart=end[i】; outputresult(select,N); return 0; 15.2.3区间覆盖问题 【例15.3】区间覆盖问题。 用i米表示x坐标轴上坐标为-1，门的长度为1的区间，并给出M(1≤M≤200)个不 同的整数，表示M个这样的区间。现在要求画几条线段覆盖住所有的区间，条件是：每条 线段可以任意长，但是要求所画线段的长度之和最小，并且线段的数目不超过N(1≤N≤ 50) 例如，给出M=5,整数1、3、4、8和11表示区间，要求所用线段不超过N=3条，如 图15.2所示。 在图15.2所示的4个覆盖方案(1、2、B和4)中，方案4是最佳的，线段的总长 度为6。事实上方案4正是这个任务的答案。 分析： 设置一个整型数组position[M来表示所有的区间，假设position[M]已经按从小到大的 顺序排好。 4: ●●8 8 3 4 Total M-5 0 12 3456789101 图152区间覆盖图例 如果N≥M,那么用M条长度为1的线段可以覆盖住所有的区间，所求的线段总长 为M 如果N<M,显然M>1,可以按照如下的贪心策略来解决：如果N=1,即要用一一条线 段覆盖住所有区间，很显然所需线段总长即为position[M-1-position+1:如果N-2,即 10
10 select[i]=1; timestart=end[i]; } i++; } outputresult(select,N); return 0; } 15.2.3 区间覆盖问题 【例 15.3】 区间覆盖问题。 用 i 来表示 x 坐标轴上坐标为[i–1，i]的长度为 1 的区间，并给出 M（1≤M≤200）个不 同的整数，表示 M 个这样的区间。现在要求画几条线段覆盖住所有的区间，条件是：每条 线段可以任意长，但是要求所画线段的长度之和最小，并且线段的数目不超过 N（1≤N≤ 50）。 例如，给出 M=5，整数 1、3、4、8 和 11 表示区间，要求所用线段不超过 N=3 条，如 图 15.2 所示。 在图 15.2 所示的 4 个覆盖方案（f1、f2、f3 和 f4）中，方案 f4 是最佳的，线段的总长 度为 6。事实上方案 f4 正是这个任务的答案。 分析： 设置一个整型数组 position[M]来表示所有的区间，假设 position[M]已经按从小到大的 顺序排好。 8 11 1 3 4 f1： f2： f3： f4： 0 1 2 3 4 5 6 7 8 9 10 11 M=5 6 7 8 8 Total length 图 15.2 区间覆盖图例 如果 N≥M，那么用 M 条长度为 1 的线段可以覆盖住所有的区间，所求的线段总长 为 M。 如果 N<M，显然 M>1，可以按照如下的贪心策略来解决：如果 N=1，即要用一条线 段覆盖住所有区间，很显然所需线段总长即为 position[M–1]–position[0]+1；如果 N=2，即