首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
65
问题
(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,将解答填入对应栏内。[说明]GPRS作为GSM分组数据的一种业务,很大程度上拓展了GSM无线数据业务空间。下面将结合中国移动近期准备在中国移动网上开展的业务介绍GPRS业务解决方案,主要包括
请问无线局域网的工作模式有哪几种?当不使用AP时,必须把一组需要互相通信的无线网卡的什么值设为相同?
从图7-1中可以看出采用什么拓扑结构与设计方法?为了进一步简化系统,有人建议把“电脑模块”与“电话模块”合成一个模块,其传输介质共用,这可以实现吗?
将图2-2中(1)和(2)空缺名称填写在对应的解答栏内。在本质上,ADSL采用的什么多路复用方式?
目前,通过移动电话接入互联网所采用的主要技术是什么?公司网络中的设备或系统(包括存储商业机密的数据库服务器、邮件服务器,存储资源代码的PC、应用网关、存储私人信息的PC、电子商务系统)中,哪些应放在DMZ中,哪些应放在内网中?并请给予简要说明。
阅读以下说明,回答问题1~4。【说明】A公司用一台Web服务器和一台应用服务器来管理销售信息。销售人员在办公室时通过PC机来访问应用服务器,若在公司以外,则通过具有数据显示功能的移动电话或PDA(PersonalDigitalAssi
如何根据网络流量选择联网设备,给出所选设备的作用。在我国,目前可供选择大的用户选择的接入方式有哪些,各自的接入速率为多少?
在图8-12所示的拓扑结构中的代理服务器上依次单击“开始→程序→管理工具→路由与远程访问,并在系统弹出的界面中打开“IP路由选择”目录树,然后用鼠标右键单击“NAT/基本防火墙”,选择[新增接口]命令。接着若选择接口1的“本地连接”,最后进行如图8-13所
在图8-12所示的拓扑结构中的代理服务器上依次单击“开始→程序→管理工具→路由与远程访问,并在系统弹出的界面中打开“IP路由选择”目录树,然后用鼠标右键单击“NAT/基本防火墙”,选择[新增接口]命令。接着若选择接口1的“本地连接”,最后进行如图8-13所
随机试题
机关、团体、部队和企事业单位因特殊需要必须租用城市私有房屋时,必须经()批准。
公共关系广告的重要作用是()
阅读下列短文,回答有关问题。阳光的香味林清玄我遇见一位年轻的农夫,在南方一个充满阳光的小镇。那时是春末,一季稻谷刚刚收成,春日阳光的金
《中华人民共和国药典》所用药筛工业筛目数(孔/英寸),下列错误者为
某女,35岁。广州某医院护土,2003年4月3日救治不明原因肺炎患者后,开始出现发热,体温39.5℃,头痛、乏力。查:血常规4.12×109/L。胸片示双肺无异常发现。此患者的诊断是
患者张某,女性,70岁,因脑出血昏迷入院,入院时患者体温38℃,脉搏100次/分,R30次/分,血压200/120mmHg。经药物治疗后血压降160/90mmHg,仍处于昏迷状态。现需鼻饲饮食。应采取的措施是()
甲公司是一家在上海证券交易所挂牌交易的制造类企业,有关股权投资业务如下:(1)2015年1月1日,甲公司以银行存款3000万元从非关联方处取得乙公司60%的股权,能够对乙公司实施控制。当日乙公司可辨认净资产的账面价值为3920万元(其中,股本1800万元
赵青一定是一位出类拔萃的教练。她调到我们大学执教女排才一年,球队的成绩突飞猛进。以下哪项,如果为真,最有可能削弱上述论证?
设f(x)在上具有连续的二阶导数,且f’(0)=0.证明:存在ξ,η,ω∈使得f’(ξ)=
TheDemocrats’TradeTroublesLastweekHousespeakerNancyPelosiandCongressmanCharlesRangelshowedgenuineleadershipb
最新回复
(
0
)