C-编程贪心法-装船-事件-删数

1、1第十章 贪心法 教学目标 贪心法解题的一般步骤 贪心法的相关理论 贪心法解题的注意事项 内容要点 贪心法的应用 贪心法解题的一般步骤 贪心法的相关理论 贪心法解题的注意事项3引子（任务10.1）：事件序列的长度问题事件序列长度：由N个在时间上不重叠的事件所组成的事件序列，其长度定义为N。已知有若干事件，发生和结束的时刻等信息数据如下所示（见下页）。试编程求出所给数据中最长的事件序列，即应由哪些事件组成一个事件序列，能使序列所含的事件数最多。4 事件号按结束时刻从小到大排序 事件号 # 0 1 2 3 4 5 6 7 8 9 10 11发生时刻 1 3 0 3 2 5 6 4 10 8 15

2、15结束时刻 3 4 7 8 9 10 12 1415 18 19 20 5 0 1 2 3 4 5 6 7 8 9 10 110 1 2 3 4 5 6 7 8 9 11 13 15 17 19 10 12 14 16 18 20 ？请思考以下3种场景：围棋开局 抢占盘面大场购物付款 纸币张数最少高考招生 成绩择优录取问题的求解思路，通常就在生活中的不经意处！7【任务 10.2】装船问题王小二毕业后从事船运规划工作。吉祥号货轮最大载重量为M吨，有N件货物供选择装船，每件货物的重量和价值是不同的。王小二的任务是从N件货物中挑选若干件上船，在满足货物总重量小于等于M的前提下，运走的货物的总价值最

3、大。 8 王小二很聪明，他选择了贪心策略，专挑价钱高重量轻的货物往船上搬。 具体方法是：对每件货物，计算其价值与重量之比，姑且称之为 “价重比”，价重比高的货物优先装船，每装一件累计其重量，控制总重量不超过货轮的载重量M。 由此，他荣幸地获得一个绰号：“贪心的王小二”。这类问题称为 0-1 背包问题。91 . 定义一个描述货物的结构 goodsstruct goods /定义名为 goods 的货物的结构 float w; /货物重量w float p; /货物价值p float pw; /货物的价重比pw int No; /货物的编号No g N; /以goods 为类型的结构数组 说明：g

4、oods 结构含4个成员，分别是货物重量w ,货物价值p ,货物的价重比pw 和货物的编号No 。gN 是结构数组，有N个数组元素，下标为0,1N-1. 每个数组元素的数据类型都是 goods 结构类型，用来描述每件货物。10 2. 使用 for 循环输入N件货物的数据 for(int i=0;iN;i+) /循环 / for icoutgigi.p; /键盘输入第i件货物的价值cout gig i.w; /键盘输入第i件货物的重量gi.pw = ( gi.p ) / ( gi.w ); /计算第i件货物的单位重量的价值 gi.No = i; /键盘输入第i件货物的编号 / for i 11对

5、N件货物的价值重量比进行从大到小的排序 goods temp; /定义具有goods结构的中间变量 /冒泡排序，将单位重量价值 高的货物往前排 for (int j=0; jN-1; j+) /for jfor (int k=0; kN-1-j; k+) /for kif ( g k.pw g k+1.pw) /iftemp = g k;g k = g k+1;g k+1 = temp; /if /for k /for j 12 4 使用 while 循环，贪心地搬货，将价值重量比高的优先抬上船，控制总重量不超过船的载重量M。 int sumw=0; / 定义装上船的货物的总重量，初始化为零

6、int sump=0; / 定义装上船的货物的总价值，初始化为零 int r = 0; / 定义变量r, 初始化为零 while ( (rN) & (sumw+ g r.w)=M) ) / 当上船货物（件数受限）总重量小于M, /while sumw = sumw + g r.w; / 记录货物总重 sump = sump + g r.p; / 记录货物总价值 r = r+1; / 试下一件货物 /while cout装货总重量 w= sumwendl; / 输出装货总重量 cout装货总价值 p= sumpendl; / 输出装货总价值 13 /* * 程序名： 10_1.cpp ( 装船问

7、题) * 作 者： wuwh * 时 间： 2007年7月12日 * 备 注： 贪心算法 */#include using namespace std;const int N=10; /常量，货物总件数struct goods /定义 goods 结构float w; /货物重量float p; /货物价值float pw; /货物单位重量的价值int No; /货物号 gN; /名为 g 的具有 goods 结构的结构数组int M; /货轮的最大载重量14int main() /主函数 / maincoutM; /键盘输入货轮的最大载重量cout最大载重量M = M; /显示信息coute

8、ndl; /空行 for(int i=0;iN;i+) /循环：输入N 件货物信息 / for icoutgigi.p; /键盘输入第i件货物的价值coutgigi.w; /键盘输入第i件货物的重量gi.pw=(gi.p)/(gi.w); /计算单位重量的价值gi.No=i; / 第i件货物的编号 / for i 15 goods temp; /定义具有 goods 结构的中间变量 for ( int j=0; jN-1; j+) /冒泡排序，将单位重量价值高的货物往前排 /for jfor ( int k=0; kN-1-j; k+ ) /for kif ( gk.pw gk+1.pw )

9、/iftemp=gk;gk=gk+1;gk+1=temp; /if /for k /for j16for(int t=0;tN;t+) /调试用,查看排序结果 cout*endl;coutNo= gt.Noendl; coutpw= gt.pwendl; coutp= gt.pendl; coutw= gt.wendl; cout*endl; /下面使用贪心策略装船17int sumw=0; / 定义装上船的货物的总重量，初始化为零int sump=0; / 定义装上船的货物的总价值，初始化为零 int r=0; / 定义变量r,初始化为零while ( rN & (sumw+gr.w)=M

10、) / 当上船货物（件数受限）总重量小于M /while sumw=sumw+gr.w; / 记录货物总重 cout# No= gr.Noendl; / 调试用 sump=sump+gr.p; / 记录货物总价值 r=r+1; / 试下一件货物 /while cout装货总重量 w= sumwendl; / 输出 cout装货总价值 p= sumpendl; / 输出 return 0; /main任务10.1 事件序列的长度问题19 0 1 2 3 4 5 6 7 8 9 10 110 1 2 3 4 5 6 7 8 9 11 13 15 17 19 10 12 14 16 18 20 20

11、（1）任意正常的事件a，其开始时刻肯定是小于结束时刻的，即：Begina = Enda。 如下两条结论是显然的：注：Begina, Enda分别指事件a的开始与结束时间21如下序列中各事件在时间上是不重叠的： 2#,9# 2#,8#,10# 2#,8#,11# 0#,3#,8#,10# 0#,3#,8#,11# 0#,1#,5#,8#,10# 0#,1#,5#,8#,11# 0#,1#,6#,10# 0#,1#,6#,11#这是包含的事件数最多22每一次，都选择最早结束的序列即“贪心策略”。于是得：0#-1#-5#-8#-10#即是最长的事件序列 ！23 #include using name

12、space std; const int N=12; /定义N 是常数12 / 定义输出选出的事件的子函数 void OtputResult(int SelectN); cout“ 0”; for( int i=1; iN; i+ ) if ( Select i =1) cout“,” i ; cout “ “ endl; 24 int main( ) int 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 SelectN=0; /预置12个事件都还未选,0为未选,1为已选 int

13、i=0;/ i 为待选事件号,预置为0号 int TimeStart=0; /当前可选事件的最早开始时间预置为025 while( i =TimeStart ) Select i =1; / 选中事件 i TimeStart=End i ; / 记住下一个事件的最早开始时间 i +; /事件号加1 OutputResult ( Select ) ;/ 调用输出子函数 return 0; 26 Beging 1 3 0 3 2 5 6 4 10 8 15 15 0 1 2 3 4 5 6 7 8 9 10 11 End 3 4 7 8 9 10 12 14 15 18 19 20 0 1 2 3

14、 4 5 6 7 8 9 10 11 Select 1 1 0 0 0 1 0 0 1 0 1 0 0 1 2 3 4 5 6 7 8 9 10 11 27任务 10.3 删数问题 设一个 由N 位数字组成的数字串（第一个数字为非零数），如果要从中删去 M 个数字，并且使剩下的数字串所表示的正整数数值最小，请问该最小数值多少？28 解题思路 从一个例子开始分析: 5 0 2 6 7 5 3 9 箭头表示 0 2 6 7 5 3 9 值高 值低 0 2 6 5 3 9 0 2 5 3 9 0 2 3 9 0 2 3 9 2 3 929 总结算法: 1. 用键盘输入数字串S; 2. 测 S 的串长

15、 L; 3. 输入要删除的数字个数 M; 4. 当 ( M0 )时, 做 i=0; 当 ( i L 且 S i =S i +1 )时， 做 i = i +1; 删去 S i ; M-; 5. 去掉 S 串中的高位 0.30#include #include using namespace std; void deleteS(char *p)；/ 删字符子函数/ 删除当前所指字符，后续字符应向前补上31int main() cout 请输入数字串: S;int L = strlen(S);cout 请输入须删掉多少个数:Mendl;int M;do cout 0 M 数字串的长度 M; whil

16、e ( M= L ); 32while(M0)int i = 0;while( (i L) & (Si = Si+1) ) i+; / 寻找待删除的数Si) deleteS(&Si); / 删除Si/ or: deleteS(S+i); M-;33/ 删除S串中高位的所有0while (S0 = 0) / 字符串首位为0deleteS(&S0); / 删掉 / or: deleteS(S);if ( strlen(S) != 0 ) / 字符串长不为0cout S endl; else / 字符串长为0cout 0 endl;/ 删空了！return 0; / main() END!34/ 删除字符序列（数组）首字符的子函数void deleteS(char *p) while (*p) / 当p所指向的字符不是终止符 *p = *(p+1); / p+1所指向的字符覆盖p所指向的字符 p+; / 删除当前所指字符，后续字符应向前补上35s0 p p+1 p=&s3 p+1=&s4 0 2 6 7 5 3 9 0 0