首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
2015-06-03
51
问题
阅读下列说明和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
表示第i+1个集装箱当前已经装入货物的体积,下标从0。
i,j:循环变量。
k:所需的集装箱数。
min:当前所用的各集装箱装入了第i个货物后的最小剩余容量。
m:当前所需要的集装箱数。
temp:临时变量。
(2)函数firstfit。
int firstfit(){
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。
int bestfit() {
int i,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>0&&temp
(3);
m=j;
}
}
(4);
k=k>(m+1)?k:(m+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是实现最先适宜策略的,从程序不难看出,第(1)空所在的for循环,就是要将n各货物装入到集装箱。根据算法的描述,是依次从第一个集装箱找,找到合适的就装入货物,依次没装入一个货物,都是依次从第一个集装箱找。结合后面的程序不难知道j标识这当前是第几个集装箱。因此每装入一个货物后,要将j清0,标识从头再找,因此第(1)空的答案是j=0。而接下来的while循环,从其条件表达式C-b[j]
不难知道,是比较当前集装箱和当前货物的体积大小,如果当前集装箱体积小,则比较下一个集装箱;否则,就应该将货物装入该集装箱,并且调整集装箱剩余体积的大小。在本题中,这个是通过数组b来实现的,因此第(2)空的答案应该为b[j]=b[j]+s
。
第(3)和第(4)空是在函数bestfit下,这个函数是实现最优适宜策略的。从程序中不难看出,for(j=0;j
0&&temp
。
在本题中,不管是采用最先适宜策略,还是最优适宜策略,它们都是根据不同策略选择目前看来最优的情况,这都属于贪心算法的思想。从两个函数不难看出,其时间复杂度是一样的,都是O(n
2
)。
第3个问题,其实是这个题目中最简单的问题,也是算法的一个实际应用。对于这个实例,如果采用最先适宜策略,那么货物{4,2,3}存放在第一个集装箱,而{7,2}存放在第二个集装箱,{5,4}存放在第三个集装箱,{3,6}存放在第四个集装箱,而{2}存放在第五个集装箱。
如果采用最优适宜策略,那么货物{4,2,4}存放在第一个集装箱,而{7,3}存放在二个集装箱,{5,2,3}存放在第三个集装箱,{6,2}存放在第四个集装箱。
因为这两种方法都是采用的贪心策略,那么在一般情况下,是不能确保得到最优解的。
转载请注明原文地址:https://kaotiyun.com/show/upDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,回答问题1至问题3。【说明】如图5-1所示,某单位通过2M的DDN专线接入广域网,该单位内网共分为三个子网。服务器放置在子网192.168.5.0/24中,财务部工作站放置在子网192.168.10.0/24,销售部工作站放置在子网
假定提供Web服务的两台Linux服务器IP地址分别为192.168.1.10和192.168.1.20。为了使用DNS循环机制,由主机名www.test.com对外提供一致的服务,需要在DNS服务器的test.com区域文件中增加下列内容:www
阅读以下说明,回答问题1和问题2,将解答填入对应的解答栏内。【说明】某单位内部网络拓扑结构如下图所示,在该网络中采用RIP路由协议。
为了使DNS_Server1能正确解析本地Web站点的域名,需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中,新建的区域名称是(1);在图2所示的对话框中,添加的新建主机名称为(2),IP地址栏应填入(3)。在客户端除了可以用p
为了使DNS_Server1能正确解析本地Web站点的域名,需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中,新建的区域名称是(1);在图2所示的对话框中,添加的新建主机名称为(2),IP地址栏应填入(3)。如下图所示,配置允许
与ISDN相关的网络设备主要有TA、NT1、NT2、TE1、TE2等。在图2-9所示的网络拓扑结构中,路由器Router1和ISDN之间是否需要加入终端适配器(TA)?请用150字以内的文字简要说明理由。在以上路由器Router2的配置命令列表中,di
阅读以下说明,回答【问题1】~【问题4】,将解答填入答题纸的对应栏内。【说明】设有A、B、C、D四台主机都处在同一个物理网络中,A主机的IP地址是192.155.12.112,B主机的IP地址是192.155.12.120,C主机的IP地址是19
阅读以下某单位宽带网络接入的技术说明,根据要求回答问题1至问题6。【说明】接入网(AN)泛指用户网络接口(UNI)与业务节点接口(SNI)间实现传送承载功能的实体网络。其目标是建立一种标准化的接,方式,以一个可监控的接入网络,使用户能够获得话音、
PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(1)。PGP还可以对电子邮件进行认证,认证机制是用MD5算法产生(2)位的报文摘要,发送方用自己的RSA私钥对(3)进行加密,附加在邮件中进行传送。公钥只用来加密(4),文件是用
L2TP协议是一种基于(1)协议的二层隧道协议,它结合了Cisco的L2F和MicrosoftPPTP的优点。该协议报文在传输层封装(2)协议之上,为了保证传输的可靠性,L2TP协议对控制报文采取了(3)机制,并要求tunne1对端设备在隧道(tunne
随机试题
杜通疏螺旋体的主要传播媒介是
A.庆大霉素B.加替沙星C.多西环素D.头孢哌酮E.阿莫西林易导致牙齿染黄的药品是()。
城镇体系规划的期限一般()年。
西安市民赵女士一家最近购买了一套总价60万元的新房,首付20万元,贷款总额40万元,其中公积金贷款10万,期限10年,年利率4.5%,商业贷款30万,期限20年,年利率6%。若30万元商业贷款采用等额本金方式还款,利息总额为______。
按照中国证监会发布的《上市公司证券发行管理办法》,要求主板(中小企业板)上市的上市公司财务状况良好,下列哪项说法是正确的()。
股票发行采用代销方式,代销期限届满,向投资者出售的股票数量未达到拟公开发行股票数量()的,为发行失败。
__________是学生活动与交往的基本场所。
布鲁内莱斯基设计的()被誉为共和政体的纪念碑。
(2010—单选—33)中国共产党领导的多党合作与政治协商制度是我国一项基本政治制度,遵守宪法和法律是多党合作的根本活动准则。这一准则的基本内容包括()。①各民主党派与共产党一样,得到宪法的承认和保护②各民主党派法律地位平等③各政党在政治生活
0,3,3,12,21,()
最新回复
(
0
)