首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn),且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn),且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装
admin
2013-07-09
27
问题
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。
【说明】
设有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
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>(j+1)?k:(j+1);
}
return k;
}
(3)函数bestfit
int bestfit(){
int i,j,min,m,temp;
k=0;
for(i=0;i<n;i++){
bri]=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>(j+1)?k:(j+1);
}
return k;
}
根据说明和C代码,该问题在最先适宜和最优适宜策略下分别采用了
(5)
和
(6)
算法设计策略,时间复杂度分别为
(7)
和
(8)
(用O符号表示)。
选项
答案
(5)贪心 (6)贪心 (7)O(n
2
) (8)O(n
2
)
解析
贪心算法在解决最优化问题上是仅根据当前已有的信息作出选择,即不是从整体最优考虑,它所作出的选择只是力求局部最优。最先适宜策略和最优适宜策略均采用了该算法设计策略。
对于时间复杂度,应根据程序中循环的层数及每层循环的次数来进行计算。可以很容易的判断,这两种算法的时间复杂度均为O(N
2
)。
转载请注明原文地址:https://kaotiyun.com/show/3iDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在计算机外部设备和主存之间直接传送而不是由CPU执行程序指令进行数据传送的控制方式称为(5)________________。
内存采用段式存储管理有许多优点,但“(6)”不是其优点。
能够主动采集信息,分析网络攻击行为和误操作的实时保护策略是指(64)。
以下关于数据流图的叙述中,不正确的是______。
某开发小组为某企业开发较大规模的项目,该开发小组已经为同一行业的其他企业开发过类似的项目,且该项目需求变化很少,则最适宜采用_______开发过程模型。
数据库是按照一定的数据模型组织、存储和应用的______的集合。
若系统中有4个互斥资源R,当系统中有2个进程竞争R,且每个进程都需要i个R(i≤3)时,该系统可能会发生死锁的最小i值是________。
假设系统有n(n≥5)个并发进程,它们竞争互斥资源R。若采用PV操作,当有3个进程同时申请资源R,而系统只能满足其中1个进程的申请时,资源R对应的信号量s的值应为_______。
[Java源程序:一个简单的Web服务器]/************************************************************//*WebServer.java*//******
目前,通过移动电话接人互联网采用的主要技术是什么?公司网络中的设备或系统(包括存储商业机密的数据库服务器、邮件服务器、存储资源代码的PC机、应用网关、存储私人信息的PC机、电子商务系统)哪些应放在DMZ中,哪些应放在内网中?给予简要说明。
随机试题
杨某为其妻王某购买了某款人身保险,该保险除可获得分红外,还约定若王某意外死亡,则保险公司应当支付保险金20万元。关于该保险合同,下列哪一说法是正确的?
关于子宫收缩乏力所致的产程延长,下列正确的是
疠气的别称不包括
下列工程合同风险中,属于信用风险的有()。
进出口货物申报后确有正当理由的,经海关同意方可修改或撤销申报。下列表述中属于正当理由的是()。
上市公司发放股票股利可能导致的结果有()。
按作业层次的不同,企业的作业可以分为以下四类。其中,随产量变动而正比例变动的作业是()。
【2013年云南昭通.简答】课堂管理的基本原则有哪些.
根据所给资料,回答以下问题。2013年1~2月,规模以上工业增加值同比实际增长9.9%(以下增加值增速均为扣除价格因素的实际增长率),比2012年12月份回落0.4个百分点。从环比看,2月份,规模以上工业增加值比上月增长0.79%。分经济类型看,1~2
FordMotorCompanyreportedadrop______quarterlyprofits.
最新回复
(
0
)