首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn],且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装运这n个货物
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn],且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装运这n个货物
admin
2014-11-13
14
问题
阅读下列说明和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开始。
b:数组,长度为n,b
表示第n+i个集装箱当前已经装入货物的体积,下标从0开始
i,j:循环变量
k:所需的集装箱数
min:当前所用的各集装箱装入了第i个货物后的最小剩余容量
m:当前所需的集装箱数
temp:临时变量
(2)函数firstfit
intfirs七fit()(
inti,j;
k=0;
for(i=0;i
b
=0;
}
for(i=0;i
(1);
while(C—b[j]
){
j++;
}
(2);
k=k>(j+1)?k:(j+1);
}
returnk;
}
(3)函数bestfit
intbestfit(){
inti,j,min,m,temp;
k=0;
for(i=0;i
b
=0;
}
for(i=0;i
min=C;
m=k+1:
for(j=0;j
temp=c—b[j]一s
;
if(temp>O&&temp
(3);
m=j;
}
}
(4) ;
k=k>(j+1)?k:(j+1);
}
return k;
}
考虑实例n=10,C=10,各个货物的体积为{4,2,7,3,5,4,2,3,6,2}。该实例在最先适宜和最优适宜策略下所需的集装箱分别为(9)和(10)。考虑一般的情况,这两种求解策略能否确保得到最优解? (11)(能或否)
选项
答案
(9)5 (10)4 (11)否
解析
本问题考查对程序的具体理解和应用。对firstfit函数进行遍历的结果如下:
因此,该实例在最先适宜策略下所需的集装箱数为5。同理可对bestfit函数进行遍历,可得到该实例在最优适宜策略下所需的集装箱数为4,遍历过程可由考生自己进行,以增强对整个算法的理解。由于贪心算法在解决最优化问题上是仅根据当前已有的信息作出选择,即不是从整体最优考虑,它所作出的选择只是力求局部最优,因此这两种求解策略不能确保得到最优解。
转载请注明原文地址:https://jikaoti.com/ti/e0i7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
根据图3-1所给出的网络连接方式及相关的网络参数,区域(A)与区域(B)中计算机的网络参数配置(如图3-2所示)为:区域(A)计算机“IP地址”(范围):(1):区域(A)计算机“子网掩码”;(2);区域(A)计算机“默认网关”:(
网络设计流程通常由以下五个阶段组成:A.确定网络物理结构B.确定网络逻辑结构C.对现有网络的体系结构进行分析D.安装和维护E.需求分析根据网络开发设计的过程,给出上述五个阶段的先后排序:(1)。将答
某交换机的配置命令如下,根据命令后面的注释,填写(1)~(3)处的空缺内容,完成配置命令。Switch(config)#(1)//将交换机命名为Sw1Swl(config)#interfacevlan1Swl(config
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
销售部的网络号是(1),广播地址是(2):技术部的网络号是(3),广播地址是(4);每个子网可用的IP地址有(5)个。在网关计算机上使用以下路由命令创建两个默认的路由:routeadd-net192.168.1.0255.255.2
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址通常采用IP地址与MAC地址绑定的策略为某些设备保留固定的IP地址
请选择恰当的内容填写在(1)、(2)、(3)空白处。一般用Host表、网络信息服务系统(NIS)和域名服务(DNS)等多种技术来实现主机名和IP地址之间的转换。Host表是简单的文本文件,而DNS是应用最广泛的主机名和IP地址的转换机制,它使用(1
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
1.路由器第一次设置时,必须通过Console口连接运行终端仿真软件的计算机进行配置,此时终端仿真程序设置的波特率应为(1)b/s。2.路由器有多种配置模式,请根据以下命令提示状态,判断路由器处于何种配置模式下。Router(Config)
随机试题
大量腹腔积液的体征包括
人体内嘌呤核苷酸分解代谢的主要终产物是
DNA分子中的碱基组成是
A.头孢西丁B.亚胺培南C.氨曲南D.拉氧头孢E.克拉维酸属于p一内酰胺酶抑制剂的抗菌药是
沥青PG分级是美国SHRP计划中提出的沥青性能分级标准,它是依据沥青的路用性能进行分级。()
生产经营单位从业人员的权利不包括()。
下列选项中,满足有效利率与名义利率的差值最大的是( )。
公司制期货交易所董事长因故临时不能履行职权的,由董事长指定的副董事长或者董事代其履行职权。( )
具有期货等金融或者法律、会计专业硕士研究生以上学历的人员,申请期货公司董事、监事和高级管理人员任职资格的,从事除期货以外的其他金融业务,或者法律、会计业务的年限可以放宽( )年。
求极限
最新回复
(
0
)