首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i] (2)nv[i][j]=nv[i-1][j] (3)j=j-p[i] 问题1中伪代码的时间复杂度为(6)(用O符号表示)。
(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i] (2)nv[i][j]=nv[i-1][j] (3)j=j-p[i] 问题1中伪代码的时间复杂度为(6)(用O符号表示)。
admin
2009-02-01
56
问题
(1)nv[i-1][j]≥nv[i-1][j-p
]+v
(2)nv
[j]=nv[i-1][j] (3)j=j-p
问题1中伪代码的时间复杂度为(6)(用O符号表示)。
选项
答案
(6)O(nM),或O(n×M),或O(n*M)
解析
本题实质上是一个0-1背包问题,该最优化问题的目标函数是
max[*]ViXi(Xi=0,1)
i=1
约束函数是
[*] PiXi≤M (xi=0,1)
0-1背包问题可用动态规划策略求得最优解,求解的递归式为
[*]
其中,nv
[j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。根据上述递归式,可以很容易以自底向上的方式编写伪代码。[问题1]中伪代码的第1行到第12行计算数组nv的元素值,第1行到第4行计算i为0或者j为0时nv
[j]的值,对应递归式的第一种情况;第7行和第8行计算当j<pi时即不能选择mi时nv
[j]的值,对应递归式的第二种情况:第9到第12行对应递归式的第三种情况,故根据递归式,空(1)的答案为nv[i-1][j]≥nv[i-1][j-p
] +v
。伪代码的第13行到第19行求解哪些食物放入到套餐中,食物项从后向前考虑,若nv
[j]=nv[i-1][j],表示食物mi没有放入套餐中,即x
=0,故空(2)的答案为nv
[j]=nv[i-1][j]。相反,若食物mi放入套餐中,则x
=1,同时套餐还能选择不超过j-p
的价格的食物,故空(3)的答案为j=j-p
。
问题2的实例要求总价格不超过100,根据上述递归式,计算出要选择的食物项为 m2、m3和m4,对应的总价值为605,总价格为100。
根据问题1的伪代码,第1行到第2行、第3行到第4行以及第14行到19行的时间复杂度为O(n),第5行到第12行的时间复杂度为O(nM)。故算法总的时间复杂度为 O(nM)。
转载请注明原文地址:https://kaotiyun.com/show/f5DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
以下各项中,(51)属于需求说明书的评测内容。①系统定义的目标是否与用户的要求一致②设计的约束条件或限制条件是否符合实际③是否考虑过软件需求的其他方案④软件的行为与它必须处理的信息、必须完成的功能是否一致
在进行面向对象设计时,采用设计模式能够(29)。
风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。“建立风险条目检查表”是(18)时的活动,“描述风险的结果”是(19)时的活动。
(12)是指把数据以及操作数据的相关方法组合在同一个单元中,使我们可以把类作为软件中的基本复用单元,提高其内聚度,降低其耦合度。面向对象中的(13)机制是对现实世界中遗传现象的模拟,通过该机制,基类的属性和方法被遗传给派生类。
关于数据库索引,以下表述正确的是(57)。①如果对表创建了索引,那么更新、插入和删除表中的记录都将导致额外的系统开销。②全表扫描一定比使用索引的执行效率低。③在字段选择性很低的情况下适用索引。④一个表创建的索引越多,对系统的性能提升越大。
针对下列程序段,需要(52)个测试用例才可以满足语句覆盖的要求。 switch(value){ case 0: other=30; break; case 1:
(46)叙述是正确的。①测试用例应由测试设计人员来制定。②测试点应由测试人员确立。③测试工作展开于项目立项后,而不是代码开发完成之后。④测试对象是源代码。
在计算机体系结构中,CPU内部包括程序计数器PC、存储器数据寄存器MDR、指令寄存器IR和存储器地址寄存器MAR等。若CPU要执行的指令为:MOV R0,#100(即将数值100传送到寄存器R0中),则CPU首先要完成的操作是(1)。
模块设计中,某模块根据输入的控制信息从文件中读一个记录或者向文件中写一个记录,则其内聚类型为______。
在编译过程中,进行类型分析和检查是()阶段的一个主要工作。
随机试题
单纯性肾病综合征严重水肿者的护理措施是
关于刑事责任、犯罪、刑罚三者之间的关系,下列说法正确的是:
用以衡量公司偿付借款利息能力的指标是( )。
世界迄今仍在使用的最古老水利工程是()。
某城市的电话号码,由六位升为七位(首位数字均不为零),则该城市可增加的电话部数是()
我国最大的油田和最大的钨矿分别位于()。
甲、乙、丙三所学校的学生被安排在周一至周五参观某革命纪念馆。纪念馆每天最多只能安排一所学校,其中甲学校连续参观两天,其余学校均只参观一天,那么共有多少种安排方法?
A、 B、 C、 D、 A
以下声明语句中错误的是______。
Therelationshipbetweentechnologyanddevelopmentiscomplicated.Attimesthenegativefeaturesoftechnologyseemto______th
最新回复
(
0
)