首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
27
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
认真阅读下列有关Linux操作系统环境下配置Apache服务器的技术说明,根据要求回答问题1至问题5。【说明】随着电子商务日益普及,A公司建构了一台装有RedhatLinux9.0操作系统的虚拟服务器,为各类客户提供网上架构商务站点的Web服
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?为了保证FTP服务器的数据安全,每个在读取文件时,只能读取和执行相关文件,请问在
X.25规范对应OSI参考模型中的3层,X.25的第3层描述了分组的格式及分组交换的过程。X.25的第2层由LAPB(LinkAccessProcedure,Balanced)实现,它定义了用于DTE/DCE连接的帧格式。X.25的第1层定义了电气和
阅读以下有关网络规划的叙述,回答问题1至问题3。网络工程是一项复杂的系统工程,一般可分为网络规划、网络设计、工程实施、系统测试验收和运行维护等几个阶段。网络规划是在需求分析的基础上,进行系统可行性分析和论证,以确定网络总体方案。网络规划阶段任务完成
阅读以下说明,回答问题1至问题3。【说明】Linux环境下L2TP的配置过程如下:①从http://www.12tpd.org/download.html上下载12tpd-0.69.tar.gz软件包。②将12tpd-0.69.tar
在图8-12所示的拓扑结构中的代理服务器上依次单击“开始→程序→管理工具→路由与远程访问,并在系统弹出的界面中打开“IP路由选择”目录树,然后用鼠标右键单击“NAT/基本防火墙”,选择[新增接口]命令。接着若选择接口1的“本地连接”,最后进行如图8-13所
在图8-12所示的拓扑结构中的代理服务器上依次单击“开始→程序→管理工具→路由与远程访问,并在系统弹出的界面中打开“IP路由选择”目录树,然后用鼠标右键单击“NAT/基本防火墙”,选择[新增接口]命令。接着若选择接口1的“本地连接”,最后进行如图8-13所
造成故障1的原因是什么?如何解决?1.将故障2中(1)和(2)两处合适的答案填入相应的解答栏内。2.故障2如何解决?
阅读以下说明和交换机的配置信息,回答问题1-3。【说明】某公司下设3个部门,为了便于管理,每个部门组成一个VLAN,公司网络结构如图1-5所示。【交换机Switch1的部分配置信息】Switch1(config)#
请分别说出(1)与(2)的设备名称。假设有一个50M的文件从终端用户上传至服务器,需要的最短时间是多少?
随机试题
A、散寒止带B、开郁顺气C、理气健脾D、补气益血E、温阳散寒乌鸡白凤丸既能调经止带,又能()。
(2017年)2×16年1月1日,甲公司经股东大会批准与其高管人员签订股份支付协议,协议约定:等待期为自2×16年1月1日起两年,两年期满有关高管人员在甲公司工作且每年净资产收益率不低于15%的,高管人员每人可无偿取得10万股甲公司股票。甲公司普通股按董事
在行政诉讼中,对被诉的行政行为负举证责任的是()。
2011年全国共举办展览6830场,比2010年增加9.2%;展出面积为8120万平方米,比2010年增长8.5%;50人以上专业会议64.2万场,比2010年增加17.4%;万人以上节庆活动6.5万场,比2010年增长3%;出国境展览面积60万平方米,比
社会主义初级阶段基本经济制度,既包括作为社会主义经济基础的公有制经济,也包括不是社会主义经济基础的非公有制经济。把非公有制经济纳入到基本经济制度之中,是因为()
某电影公司计划使用IT系统把我国建国60周年国庆阅兵仪式做成一个有史以来最好的数字格式纪录片。项目承建方允许高级项目经理使用任何需要的资源,但是高级项目经理提出的能胜任此任务的最佳人选却正在执行另一个项目,可见该项目最主要的约束是(55)。
多数情况下,结构化开发方法是信息系统工程和()开发的有效方法。
关于ARM嵌入式处理器的工作状态,以下说法正确的是()。
NeitherhenorI______interestedinrockmusic.
Gotapenhandy?Tobestestimateyourstart-upcosts,you’llneedtomakealistandthemoredetailedthebetter.Asmartway
最新回复
(
0
)