首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
32
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在网络应用测试中,网络延迟是一个重要指标。以下关于网络延迟的理解,正确的是(64)
确定测试基线属于()活动。
广义的软件测试由“确认”、“验证”、“测试”三个方面组成,其中“确认”是______。A.想证实在一个给定的外部环境中软件的逻辑正确性,检查软件在最终的运行环境上是否达到预期的目标B.检测软件开发的每个阶段、每个步骤的结果是否正确无误,是否与软件开发各
下列操作系统中,_____保持网络系统的全部功能,并具有透明性、可靠性和高性能等特性。
己知某文档仅包含6种不同的字符,其每个字符出现的频率如下表所示,采用霍夫曼编码对该文档压缩存储,则单词“face”的编码为_______,该文档的压缩比为25%。
在C程序中,设有“inta=3,b=2,c=1;”,则表达式a>b>c的值是_________。
某个不确定有限自动机(s0为初态,s3为终态)如下图所示,_______是该自动机可识别的字符串(即从初态到终态的路径中,所有边上标记的字符构成的序列)。
若计算机字长为32,则采用补码表示的整数范围为______。
目前,通过移动电话接人互联网采用的主要技术是什么?目前,国内采用的第三代移动通信技术标准有哪些?
阅读以下说明,回答问题1至问题3,将解答填入答题纸对应的解答栏内。说明网络解决方案如图4-1所示。该网络原先使用的是国外品牌的交换机,随着网络规模的扩大,增添了部分国产品牌的交换机,交换机1至交换机5均是国产10M/100M自适应交换机,交换机6
随机试题
患者,男性,46岁,工人。因发热、心慌、血沉100mm/h,诊断为风湿性心肌炎。无高血压及溃疡病史。入院后接受抗风湿治疗,泼尼松每日30~40mg口服,用药至第12日,血压上升至150/100mmHg,用药至第15日,上腹不适,有压痛,第24日发现黑便,第
正常成人白细胞计数中淋巴细胞的百分比是
A.大黄根茎B.生大黄片C.酒大黄D.熟大黄E.大黄炭黑褐色,有特异香气
B区人民法院有无管辖权?乙某能否向A区人民法院起诉A区公安分局,并说明理由。B区人民法院要求A区公安分局于2002年1月6日以前提出答辩状是否正确?为什么?
甲工厂向乙大学发函表示:“我厂生产的×型电教室耳机,每副30元。如果贵校需要,请与我厂联系。”乙大学回函:“我校愿向贵厂订购×型耳机1000副,每副单价30元,但需在耳机上附加一个音量调节器。”2个月后,乙大学收到甲厂发来的1000副耳机,但这批耳机上没有
钢管混凝土拱应采用()施工,由拱脚向拱顶对称均衡地连续压注一次完成。
小明今年高中毕业,他想继续上大学,他爸爸则认为上大学费用高,而且将来工作不好找,还不如早点出去打工挣钱。小明面临着人生中一个非常重要的决策。从经济学的角度讲,上大学从根本上来说是一种经济决策,因此,与任何一种人力资本投资一样,决定是否上大学的人是需要考虑上
中国APEC峰会批准了《亚太经合组织互联互通蓝图》这一里程碑式文件,决心在2025年前实现()的远景目标,并完成共同确立的具体指标。
WhichofthefollowingwordscanNOTbeusedtocomplete"Withurbanizationthe______betweenrichandpoorsharpened"?
【B1】【B18】
最新回复
(
0
)