首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2021年下半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn},且有si≤C(1≤i≤n)。为
(2021年下半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn},且有si≤C(1≤i≤n)。为
admin
2018-07-27
77
问题
(2021年下半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn},且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装运这n个货物。
下面分别采用最先适宜策略和最优适宜策略来求解该问题。
最先适宜策略(firstfit)首先将所有的集装箱初始化为空,对于所有货物,按照所给的次序,每次将一个货物装入第一个能容纳它的集装箱中。
最优适宜策略(bestfit)与最先适宜策略类似,不同的是,总是把货物装到能容纳它且目前剩余容重最小的集装箱,使得该箱子装入货物后闲置空间最小。
【C代码】
下面是这两个算法的C语言核心代码。
(1)变量说明
n:货物数
C:集装箱容量
s:数组,长度为n,其中每个元素表示货物的体积,下标从0开始
b:数组,长度为n,b
表示第n+i个集装箱当前已经装入货物的体积,下标从0开始
i,j:循环变量
k:所需的集装箱数
min:当前所用的各集装箱装入了第i个货物后的最小剩余容量
m:当前所需的集装箱数
temp:临时变量
(2)函数firstfit
int firstfit(){
int i,j;
k=0;
for(i=0;i<n;i++){
b
=0;
}
for(i=0;i<n;i++){
_____(1);
while(C-b[j]<s
){
j++;
}
_______(2);
k=k>(j+1)?k:(j+1);
}
return k;
}
(3)函数bestfit
int bestfit(){
int i,j,min,m,temp;
k=0;
for(i=0;i<n;i++){
b
=0;
}
for(i=0;i<n;i++){
min=C;
m=k+1;
for(j=0;j<k+1;j++){
temp=C-b[j]-s
;
if(temp>0 &&temp<min){
______(3);
m=j;
}
}
______(4);
k=k>(j+1)?k:(j+1);
}
return k;
}
考虑实例n=10,C=10,各个货物的体积为{4,2,7,3,5,4,2,3,6,2}。该实例在最先适宜和最优适宜策略下所需的集装箱分别为_____(9)和_____(10)。考虑一般的情况,这两种求解策略能否确保得到最优解?_____(11)(能或否)
选项
答案
(9)5 (10)4 (11)否
解析
本问题考查对程序的具体理解和应用。
对firstfit函数进行遍历的结果如表9.4所示。
因此,该实例在最先适宜策略下所需的集装箱数为5。同理可对bestfit函数进行遍历,可得到该实例在最优适宜策略下所需的集装箱数为4,遍历过程可由考生自己进行,以增强对整个算法的理解。
由于贪心算法在解决最优化问题上是仅根据当前已有的信息做出选择,即不是从整体最优考虑,它所做出的选择只是力求局部最优,因此这两种求解策略都不能确保得到最优解。
转载请注明原文地址:https://kaotiyun.com/show/q7DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明然后完成问题1、问题2、问题3、问题4,把答案填入相应的对应栏内。[说明]如图10-1是Cisco1900交换机划分为两个vain拓扑图,把E0/10划分为vlan2,把E0/20划分为vlan3。[*]
请说出图9-1的拓扑结构名称与特点。根据IP地址与子网掩码,请判断它们是否属于同一个网段?如果不是,请说出他们分别属于哪个网段。
将图2-2中(1)和(2)空缺名称填写在对应的解答栏内。使ADSL的传输速率更高有哪两个主要因素?
下面是某路由器的部分配置信息,解释(n)处标有下划线部分的含义。【配置路由器信息】Currentconfiguration:!version11.3noservicepassword
某单位拟建立一个Intranet,建立自己的Web服务器、DNS服务器,E-mail服务器和内部业务服务器,有一批客户机联网,要求这些机器有的可以到Internet上,只允许访问自己的Web服务器。请你做出规划,解决如下问题。
阅读以下说明,回答问题1至问题3。【说明】路由器中IP访问控制列表能够帮助控制网上包的传输。
结合图7-18所示的网络拓扑结构图,将以下路由器R1配置信息中(1)~(9)空缺处的内容填写完整,实现路由器R1的正确配置。Router>en(进入特权模式)Router#
认真阅读下列有关移动用户身份认证技术的说明,根据要求回答问题1至问题4。【说明】随着无线局域网技术、3G移动通信技术的不断发展,网络资源得到了更广泛的利用。由于移动环境下的通信链路比较容易受到恶意攻击或窃听,因此在移动节点与本地代理1之间交换的登
认真阅读下列有关Linux操作系统的Samba配置技术的说明,根据要求回答问题1至问题6。【说明】SMB(ServerMessageBlock,服务消息块)协议主要用于实现Windows和Linux操作系统中计算机之间共享打印机、共享串行接
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如要封闭某用户的账号,请问在图6-4中怎么设置?
随机试题
关于主动脉夹层破口错误的是
A.重新检测茶碱浓度,增加25%剂量B.症状控制无需加量,调整剂量后重新检测茶碱浓度C.症状控制且无副作用则不调整剂量D.症状控制且无副作用也停止1次用药,减少50%剂量E.症状控制且无副作用也停止2次用药,减少不少于50%剂量茶碱浓度10~1
对淹溺病人出现心脏呼吸骤停的现场急救应最先实施
电算化后,部分会计核算的管理方法需要修改,下列说法不正确的是()。
英达公司下设A、B两个投资中心。A投资中心的投资额为200万元,投资利润率为15%:B投资中心的投资利润率为17%,剩余收益为20万元;英达公司要求的平均最低投资利润率为12%。英达公司决定追加投资100万元,若投向A投资中心,每年可增加利润20万元;若投
一般资料:求助者,男性,35岁,已婚,硕士学历,公务员。案例介绍:求助者非常要强,10余年来工作认真负责,积极努力。半年前其科长退休,上级委派他为代理科长,他因为得到认可而高兴,认为这是自己努力工僬的结果。一个多月前上级来了正式任命,但任命的科长
A、 B、 C、 D、 A奇数项图形中带曲线小图形均为外凸图形,偶数项图形中带曲线小图形均为内凹图形。
某河鱼类资源丰富,但水流湍急。有个老人在河边钓鱼,一个小孩走过去观看。老人技艺纯熟,没多久就钓到满满一篓鱼。老人见小孩很可爱,要把整篓的鱼送给他,小孩摇摇头。老人惊异地问:“你为什么不要?”小孩回答:“我要您手中的钓竿。”
关于我国封建成文法典的表述,正确的是()。
深水区(改革开放)
最新回复
(
0
)