首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
13
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在安装RedhatLinux9.0操作系统的过程中,如果没有选择安装Web服务器,Apache服务器则需要手动安装。现从http://httpd.apache.org网站上免费下载了一个apache-2.2.3RPM格式的软件包,请将以下(1)空缺处
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如想将某用户在设咸FTP服务器管理员,其用户名称不变,请问在“Privileg
指出上述解决方案存在什么问题?需要增加什么设备?如何连接?若在该局域网实现VLAN,路由器将起什么作用?
阅读以下说明,回答问题1和问题2。【说明】在一幢11层的大楼内组建一个局域网,该局域网的连接示意图如图5-4所示。
通常,在该图书馆架构无线局域网(WLAN)的设计流程需要经过以下6个阶段:A.设备软硬件安装、调试B.确定无线局域网物理结构C.确定无线局域网逻辑结构D.进行需求分析和现场调研E.验收测试和维护F.进行设备产
通常,在该图书馆架构无线局域网(WLAN)的设计流程需要经过以下6个阶段:A.设备软硬件安装、调试B.确定无线局域网物理结构C.确定无线局域网逻辑结构D.进行需求分析和现场调研E.验收测试和维护F.进行设备产
阅读以下在图书馆无线阅览室部署WLAN的技术说明,根据要求回答问题1至问题6。【说明】某图书馆已有一个66台客户机的小型局域网。由于信息化发展的要求,现有的网络不能满足读者的需求,经过对几个网络扩容方案进行分析、对比和探讨后,决定在新建的电子信息
可供使用的合法IP还有多少哪些?请写出。使用内部IP进行地址转换,若用一台主机连接内外两个网络,请说出两种不同的网络接法并进行比较?
设计该宽带路由器的多任务嵌入式实时操作系统时,由于多个任务均可能要求占用CPU这个关键资源,因此CPU的任务管理是一个非常重要的设计内容。在该实时操作系统中,任务作为占用资源的基本单位,总共有5个状态:休眠状态、就绪状态、运行状态、等待或挂起状态和中断服务
随机试题
怎样进行液压、气动系统管路与管接头的维修装配作业?
每逢不良行为出现时即给予一痛苦刺激,如电刺激、呕吐等,经过一定时间反复训练,不良行为就和不愉快体验建立了条件联系。通常用于治疗以下哪种障碍
机体对HBV有免疫力的指标是代表乙型肝炎恢复期的指标是
当承包人索赔后,工程师可以对索赔提出质疑的情况包括()。
橡胶衬里工艺中包括硫化过程,橡胶硫化的方法有()。
3年期A债券面值1000元,年利率10%,必要收益率9%;B债券年利率8%,其他同A债券,则以下说法正确的是()。
“3D打印”技术的出现,引领着消费需求。“3D打印”创新属于()。
设二次型f(x1,x2,x3)=x12+4x22+x32+2ax1x2+2bx1x3+2cx2x3的矩阵A满足AB=B,其中B=.用正交变换化二次型为标准形,并写出所用正交变换.
在希尔排序法中,每经过一次数据交换后
Intheworldofclimatechange,itisintheEarth’scoldregionswheretrendscanmosteasilybeseen.Thecryosphere,wherewa
最新回复
(
0
)