首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
23
问题
阅读下列说明和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;
}
根据说明和C代码,该问题在最先适宜和最优适宜策略下分别采用了
(5)
和
(6)
算法设计策略,时间复杂度分别为
(7)
和
(8)
(用O符号表示)。
选项
答案
(5)贪心 (6)贪心 (7)O(n
2
) (8)O(n
2
)
解析
贪心算法在解决最优化问题上是仅根据当前已有的信息作出选择,即不是从整体最优考虑,它所作出的选择只是力求局部最优。最先适宜策略和最优适宜策略均采用了该算法设计策略。
对于时间复杂度,应根据程序中循环的层数及每层循环的次数来进行计算。可以很容易的判断,这两种算法的时间复杂度均为O(N
2
)。
转载请注明原文地址:https://kaotiyun.com/show/3iDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在计算机外部设备和主存之间直接传送而不是由CPU执行程序指令进行数据传送的控制方式称为(5)________________。
能够主动采集信息,分析网络攻击行为和误操作的实时保护策略是指(64)。
以下不属于在需求分析阶段编写的文档是
某计算机系统页面大小为4K,进程P的页面变换表如下表所示。若P中某数据的逻辑地址为十六进制2C18H,则该地址的页号和页内地址分别为2和C18H;经过地址变换后,其物理地址应为十六进制______。
以下描述中,属于通用操作系统基本功能的是_______。
若计算机字长为32,则采用补码表示的整数范围为______。
目前,通过移动电话接人互联网采用的主要技术是什么?目前,国内采用的第三代移动通信技术标准有哪些?
FTTx+LAN接入方式采用什么拓扑结构?将图中(1)~(3)处空缺的传输介质名称填写到答题纸的相应位置。
认真阅读下列说明信息,回答问题1至问题5。[说明]在一个基于TCP/IP协议的网络中,每台主机都有一个IP地址,根据获得IP地址的方式不同,可以分为静态IP和动态IP。例如:用宽带入网,会有一个固定的IP地址,每次连入Internet,你的IP地
随机试题
A.明胶B.苯甲醇C.乳糖D.青霉素E.普鲁卡因醋酸亮丙瑞林对哪种物质过敏者应慎用?
整体到货的汽轮机高、中压缸,测量运输环节轴向和径向的定位尺寸,并以制造厂的装配记录校核,要在汽缸()进行。
基金产品设计包含三方面重要的信息输入:客户需求信息、投资运作信息和产品市场信息。()
根据下列资料,回答下列问题。2014年我国实施“单独两孩”生育政策,出生人口1687万人,比上年增加47万人。2016年实施“全面两孩”生育政策,出生人口1786万人,比上年增加131万人;出生率与“十二五”时期年平均出生率相比,提高了0.84个
1/3,1/15,1/35,()
托尔斯泰创造了小说艺术的巅峰,他能把拿破仑进军俄国的战争史诗般场面驾驭自如、能把安娜的人性刻画得_______,像这样的大手笔再也没有了。填入画横线部分最恰当的一项是()。
官方储备
Britishpeoplearefarmoresophisticatedaboutbeveragesthantheywere50yearsago.WitnesstheStarbucksrevolutionandyou’
WhichofthefollowingisproperdescriptionformembersofCongress?attitudetowardsBushadministration?plans?
’Diamonds’,sangMarilynMonroeinthefilmGentlemenPreferBlondes,’areagirl’sbestfriend.’Youmightnotagree,buty
最新回复
(
0
)