首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容量为C的集装箱以便运输,这n个货物的体积分别为{S1,S2,…,Sn},且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容量为C的集装箱以便运输,这n个货物的体积分别为{S1,S2,…,Sn},且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装
admin
2019-10-07
48
问题
阅读下列说明和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开始
6:数组,长度为n,b
表示第i+1个集装箱当前已经装入货物的体积,下标从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>(=i+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>(m+1)?k:(m+1);
}
return k;
}
根据说明和C代码,该问题在最先适宜和最优适宜策略下分别采用了______(5)和______(6)算法设计策略,时间复杂度分别为______(7)和______(8)(用O符号表示)。
选项
答案
(5)贪心 (6)贪心 (7)O(n2) (8)O(n2)
解析
转载请注明原文地址:https://kaotiyun.com/show/osxZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请结合图2-6所示的网络拓扑结构图及题干的相关描述信息,将图2-7所示的配置文件中的(1)~(4)空缺处的内容填写完整。请将以下(5)-(10)空缺处的内容填写完整。DHCP协议的前身是在传输层使用(5)协议的BOOTP协议,是BOOTP的增强
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]RIP(RoutingInformationProtocols,路由信息协议)是使用最广泛的距离向量协议,它是由施乐(Xerox)在70年代开发的。当时,RI
阅读以下说明,回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。[说明]Serv-U是一种被广泛运用的FTP服务器端软件,支持3x/9x/ME/NT/2000等Windows系列,利用它可以设定多个FTP服务器、限定登录用户的
阅读以下说明,回答问题1和问题2。【说明】在一幢11层的大楼内组建一个局域网,该局域网的连接示意图如图5-4所示。
阅读以下有关网络规划的叙述,回答问题1至问题3。网络工程是一项复杂的系统工程,一般可分为网络规划、网络设计、工程实施、系统测试验收和运行维护等几个阶段。网络规划是在需求分析的基础上,进行系统可行性分析和论证,以确定网络总体方案。网络规划阶段任务完成
通常,在该图书馆架构无线局域网(WLAN)的设计流程需要经过以下6个阶段:A.设备软硬件安装、调试B.确定无线局域网物理结构C.确定无线局域网逻辑结构D.进行需求分析和现场调研E.验收测试和维护F.进行设备产
阅读以下说明,回答问题1和问题2。【说明】对小范围(不超过100米)内的组网来说,最常见的为以集线器(Hub)为中心的对等式局域网。在网线的制作中,对线的标准有两个:EIA/TIA568A和EIA/TIAT568B标准。
阅读以下说明,回答问题1~6,将答案填入对应的解答栏内。某公司有一个局域网,在ISP申请了Internet接入,接入方式是以太网,ISP分配给了一个固定的IP地址为222.152.199.33、子网掩码为255.255.255.252、默认网关为2
阅读以下说明,回答问题1~3,将答案填入对应的解答栏内。网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在图4-1的设计方案中,与Internet连接的路由器采用网络地址转换。某学校通过专线上网,申请的
阅读以下说明,回答问题1~5,将答案填入对应的解答栏内。某公司在国际网互联中心申请了210.45.12.0/24一个C的IP地址,域名为abc.com.cn。该公司有一台该WEB服务器(IP地址为210.45.12.11,主机名为S1)、一台FT
随机试题
下列选项中,属于社会公德内容的有
Thereisonethingthateveryonewantsmorethananythingelse.Somepeopletrytogetitbymakingmoney.Theythinkthatwhen
秦先生,高血压病,近期血压波动较大,为该病人测量血压时应做到
关于慢性胃炎的叙述,正确的是()。
根据《公司登记管理条例》的规定,自治区、直辖市工商行政管理局负责本辖区内()的登记。
大宇电子有限公司为一般纳税人,增值税率17%。2007年因生产经营所需要,于年初开始自营建造厂房一幢,发生如下业务,要求:根据以下业务编制会计分录。4月30日经查明原因,定额内损耗3000.00元,不可抗力发生意外损耗11000.00元,仓库保管员玩
中国近代葡萄酒酿造业始于()。
某市工商局春节期间出台叫停“禁止自带酒水”等六项措施,引起了中国烹饪协会高调反弹,工商部门作出解释声明:这是对于不规范行为的合法做法。此事件引起社会极大反响,并持续发酵!请问你怎么看?
人民检察院决定逮捕犯罪嫌疑人、被告人的,由人民检察院执行。()
下列可以激活属性窗口的操作是()。
最新回复
(
0
)