首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
30
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下关于FTTC宽带接入Internet的技术说明,根据要求回答问题1至问题5。【说明】光纤接入网(OpticalAccessNetwork,OAN)是以光纤为传输媒体,并利用光波作为光载波传送信号的接入网。FTTC+LAN是实现居民宽带
请结合图2-6所示的网络拓扑结构图及题干的相关描述信息,将图2-7所示的配置文件中的(1)~(4)空缺处的内容填写完整。在图2-7所示的配置文件中,第14行至第18行实现什么配置功能?
阅读以下有关网络规划的叙述,回答问题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所
通常,在该图书馆架构无线局域网(WLAN)的设计流程需要经过以下6个阶段:A.设备软硬件安装、调试B.确定无线局域网物理结构C.确定无线局域网逻辑结构D.进行需求分析和现场调研E.验收测试和维护F.进行设备产
阅读以下在图书馆无线阅览室部署WLAN的技术说明,根据要求回答问题1至问题6。【说明】某图书馆已有一个66台客户机的小型局域网。由于信息化发展的要求,现有的网络不能满足读者的需求,经过对几个网络扩容方案进行分析、对比和探讨后,决定在新建的电子信息
阅读以下说明,回答问题1~3。【说明】网络解决方案如图2-5所示,该网络原先使用的使国外品牌的交换机,随着网络规模的扩大,增添了部分国产品牌的交换机,交换机1~5均是国产10M/100Mbit/s自适应交换机,交换机6和交换机7是第3层交换
请阅读以下说明和Socfort程序,将应填(n)处的字句写在对应栏内。网络应用的基本模型是客户机/服务器模型,这是一个不对称的编程模型,通信的双方扮演不同的角色:客户机和服务器。以下是一个简单的客户机程序(服务器程序略),其工作过程非常简单:客
阅读以下说明,回答问题1~6,将答案填入对应的解答栏内。某公司有一个局域网,在ISP申请了Internet接入,接入方式是以太网,ISP分配给了一个固定的IP地址为222.152.199.33、子网掩码为255.255.255.252、默认网关为2
随机试题
背景某学校食堂装修改造项目采用工程量清单计价方式进行招投标,该项目装修合同工期为4个月,合同总价为500万元,合同约定实际完成工程量超过估计工程量10%以上时调整单价,调整后综合单价为原综合单价的90%。合同约定厨房铺地砖工程量为5000m2,单价为89
现代领导工作的核心任务是科学决策和有效地组织决策实施,以实现【】
A.肝肠循环B.首关消除C.一级动力学消除D.零级动力学消除E.生物利用度药物从给药部位到达全身血循环的相对分量和速度,称为()
非全日制用工报酬结算支付周期最长为()
以下体现了建设工程项目质量目标的具体定义过程的有()。
某电子玩具零件厂靠外墙的采用自然排烟的防烟楼梯间,每______层内可开启的外窗总面积之和不应小于______m2。()
打开报表平台,设置报表公式。打开考生文件夹下的“资产负债表—B2.srp”,完成下列操作后,将报表以源文件名进行保存。判断并设计单元格B36和C36的计算公式。
()是教师专业发展的核心概念。
按照集线器是否能够堆叠,集线器可分为可堆叠式集线器和______。
InproposingAsuchphilanthropicdonations,thedirectorofthecompanycertainlyspokeBfromagenuineconcernCfortheneedya
最新回复
(
0
)