首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn),且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn),且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装
admin
2013-07-09
31
问题
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。
【说明】
设有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++){
bri]=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)。该实例在最先适宜和最优适宜策略下所需的集装箱分别为
(8)
和
(10)
。考虑一般的情况,这两种求解策略能否确保得到最优解?
(11)
能或否)
选项
答案
(9)5 (10)4 (11)否
解析
本问题考查对程序的具体理解和应用。
对firstfit函数进行遍历的结果如下:
因此,该实例在最先适宜策略下所需的集装箱数为5。同理可对bestfit函数进行遍历,可得到该实例在最优适宜策略下所需的集装箱数为4,遍历过程可由考生自己进行,以增强对整个算法的理解。
由于贪心算法在解决最优化问题上是仅根据当前已有的信息作出选择,即不是从整体最优考虑,它所作出的选择只是力求局部最优,因此这两种求解策略不能确保得到最优解。
转载请注明原文地址:https://kaotiyun.com/show/CiDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
某文件管理系统在磁盘上建立了位示图(bitmap),记录磁盘的使用情况。若系统中字长为32位,磁盘上的物理块依次编号为:0、1、2、…,那么8192号物理块的使用情况在位示图中的第(12)个字中有所描述。
若浮点数的阶码用移码表示,尾数用补码表示。两规格化浮点数相乘,最后对结果规格化时,右规的右移位数最多为(2)位。
某软件设计师自行将他人使用C程序语言开发的控制程序转换为机器语言形式的控制程序,并固化在芯片中,该软件设计师的行为(15)。
在软件开发过程中,常采用图形表示相关的信息,(28)不用于表示软件模块的执行过程。
以下关于数据流图的基本要素的叙述中,不正确的是_______。
[Java源程序:一个简单的Web服务器]/************************************************************//*WebServer.java*//******
目前,通过移动电话接人互联网采用的主要技术是什么?进行一次查询的数据信息如表9-1所示,网络的基本通信服务费用如表9-2所示,总费用=网络租用费+通信费。根据表中给出的数据,试计算销售员每月至少应进行多少次查询,才能使得使用移动电话的总费用比使用PDA
阅读以下说明,回答问题1至问题3,将解答填入答题纸对应的解答栏内。说明网络解决方案如图4-1所示。该网络原先使用的是国外品牌的交换机,随着网络规模的扩大,增添了部分国产品牌的交换机,交换机1至交换机5均是国产10M/100M自适应交换机,交换机6
阅读下面的说明,回答问题1至问题5。[说明]利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个虚拟子网,可以对各个子网实施不同的管理策略。下图表示两个交换机相连,把6台计算机配置成两个VLAN。
请认真阅读下列有关计算机网络防火墙的说明信息,回答问题1~5。[说明]某单位的内部局域网通过防火墙与外部网络的连接方式及相关的网络参数如下图所示。
随机试题
可使肥厚型心肌病杂音增强的因素是
孕妇36周妊娠,自述于翻身、行走时经常出现腹部发紧,无痛感,阴道检查宫口未开,宫颈管未消失,此时最恰当的诊断为
患者,女性,25岁,2年来有发作性神志丧失,四肢抽搐,服药不规律,今日凌晨又有发作,意识一直不清醒,来院后又有一次四肢抽搐发作。癫痫患者在辅助检查中最重要的手段是
招标人对已发出的招标文件进行必要的澄清或者修改,应当在招标文件要求提交投标文件截止时间至少()前发出。
建筑高度大于()m的住宅建筑为一类高层民用建筑。
()是保证旅游团的各项旅游活动按计划顺利实施的重要方面。
普通中小学美术教育的目的主要是()。
邢某与牛某订立了一份买卖合同。双方在合同中约定邢某须于6月30日向牛某预付定金20万元。6月30日邢某未支付定金,经牛某催告后邢某仍未支付。对此牛某的哪些诉讼请求法院不予支持()。
设单位质点在水平面内作直线运动,初速度v|t=0=v0.已知阻力与速度成正比(比例系数为1),问t为多少时此质点的速度为并求到此时刻该质点所经过的路程.
A、Shethinksthemanshouldhavepaidmuchattentiontothesociety.B、Shethinksthemanhasshownmuchconcernaboutcommonpe
最新回复
(
0
)