首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
52
问题
(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在某大学学籍管理信息系统中,假设学生年龄的输入范围为16~40,则根据黑盒测试中的等价类划分技术,下面划分正确的是(46)。
从数据库管理系统的角度看,数据库系统一般采用如下图所示的三级模式结构。图中①②处应填写(26),③处应填写(27)。
设有职工EMP(职工号,姓名,性别,部门号,职务,进单位时间,电话),职务JOB(职务,月薪)和部门DEPT(部门号,部门名称,部门电话,负责人)实体集。一个职务可以由多个职工担任,但一个职工只能担任一个职务,并属于一个部门,部门负责人是一个职工。下图所示
风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。“建立风险条目检查表”是(18)时的活动,“描述风险的结果”是(19)时的活动。
用等价类划分法设计8位长数字类型用户名登录操作的测试用例,应该分成(44)个等价区间。
在计算机体系结构中,CPU内部包括程序计数器PC、存储器数据寄存器MDR、指令寄存器IR和存储器地址寄存器MAR等。若CPU要执行的指令为:MOV R0,#100(即将数值100传送到寄存器R0中),则CPU首先要完成的操作是(1)。
针对电子政务类应用系统的功能测试,为设计有效的测试用例,应(34)。
一个软件系统的生存周期包含可行性分析和项目开发计划、需求分析、设计(概要设计和详细设计)、编码、测试和维护等活动,其中(18)是软件工程的技术核心,其任务是确定如何实现软件系统。
软件测试原则中指出“完全测试是不可能的”,主要原因是______。A.输入量太大、输出结果太多以及路径组合太多B.自动化测试技术不够完善C.测试的时间和人员有限D.仅仅靠黑盒测试不能达到完全测试
如果在程序中的多个地方需要使用同一个常数,那么最好将其定义为一个符号常量,这样______。
随机试题
可出现胆囊显著肿大无压痛,伴黄疸进行性加重的疾病是
护士误给某青霉素过敏患者注射青霉素,造成患者死亡。此事故属于
首席风险官存在下列情形时,期货公司董事会可以免除其职务的有()。
在会员制期货交易所中,()负责审查人会申请,并调查其真实性及申请人的财务状况、个人品质和商业信誉。
甲企业为增值税一般纳税人,采用计划成本进行材料日常核算,有关资料如下:(1)2004年12月31日资产负债表年初数如下表所示:资产负债表(简表)编制单位:甲公司2004年12月
CH3CH==CH2+HBr________。
某部门共有5人,有以下三个命题:①部门中有部分人是女生;②部门中有部分人是男生;③部门经理是男生,已知这三个命题中有且仅有一个是真的,由此可以推出该部门()。
某公司三个部门向灾区捐款,甲部门捐款数是另外两个部门捐款数的,乙部门捐款数是另外两个部门捐款数的。已知丙部门捐款1800元,则这三个部门共捐款()。
Whatisthistalkmainlyabout?
Theunderlinedword"address"inparagraph2isclosestinmeaningto"______".Thenation’seconomicfocalpointwasnowfocus
最新回复
(
0
)