首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
26
问题
(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
针对程序段:IF(X>10)AND(Y<20)THEN W=W/A,对于(X,Y)的取值,以下(56)组测试用例能够满足判定覆盖的要求。
针对下列程序段,需要(52)个测试用例才可以满足语句覆盖的要求。 switch(value){ case 0: other=30; break; case 1:
黑盒测试中,(59)是根据输出对输入的依赖关系设计测试用例。
关于bug管理流程,______是正确的做法。A.开发人员提交新的bug入库,设置状态为“New”B.开发人员确认是bug,设置状态为“Fixed”C.测试人员确认问题解决了,设置状态为“Closed”D.测试人员确认不是bug,设置状态为“Reo
以下关于白盒测试和黑盒测试的理解,正确是______。A.白盒测试通过对程序内部结构的分析、检测来寻找问题B.白盒测试通过一些表征性的现象、事件、标志来判断内部的运行状态C.单元测试可应用白盒测试方法,集成测试则采用黑盒测试方法D.在软件生命周期各
已知文法G:S→A0|B1,A→S1|1,B→S0|0,其中S是开始符号。从S出发可以推导出()。
针对以下C语言程序段,假设sta[10]=-1,对于x的取值,需要______个测试用例能够满足分支覆盖的要求。intMathMine(intx){intm=0;inti;for(i=x-1;i<=x+1;
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则___________(41)是一个大项堆结构,该堆结构用二叉树表示,其高度(或层数)为___________(42)。(42)
设系统中有R类资源m个,现有n个进程互斥使用。若每个进程对R资源的最大需求为w,那么当m、n、w取下表的值时,对于下表中的a~e五种情况,(26)两种情况可能会发生死锁。对于这两种情况,若将(27),则不会发生死锁。
随机试题
注册商标专用权所有人可以是()()()()。
现有前后两段落且段落格式也不同,当删除前一个段落标记时下列哪项正确()
A.眼睑不能闭合B.上睑下垂,眼球向上、向下、向内运动障碍C.眼球向下、向外运动减弱D.眼球向外转动障碍E.视物模糊动眼神经损害
脑复苏中首选的脱水剂为
噪声预测范围一般应()噪声评价等级所规定的范围。
【背景资料】某炼油厂管道安装为一个独立的单位工程,进行分部工程验收时,发现热力管道有几个钢制固定支架的主要受力构件尺寸小于设计尺寸,经原设计单位核算不能满足使用要求。【问题】分部工程验收时对质量检测有何要求?分部工程的质量等级应如何评定?
关于仲裁庭的说法,错误的是()。
D公司预期未来每年产生的永续现金流量在经济状况好的情况下为1500万元,经济状况不好的情况下只有500万元,预计经济状况好的可能性为60%,经济状况不好的可能性为40%。要求:假设企业处于完美资本市场中,如果企业借入了5000万元的债务,债务的期望报
TheUnitedStates【C1】______alargepartoftheNorthAmericancontinent.ItsneighborsareCanada【C2】______thenorth,【C3】______M
TherelationshipbetweenlanguagelearningstrategypreferencesandEnglishproficiencyamongstudentspuzzlesmanyEnglishlea
最新回复
(
0
)