首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
66
问题
(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
针对以下C语言程序段,对于(MaxNum,Type)的取值,至少需要(62)个测试用例能够满足判定覆盖的要求。while(MaxNum-->0){if(10==Type)x=y*2;elseif(100==Type)
用等价类法划分Windows文件名称,应该分成(39)—个等价区间。
从数据库管理系统的角度看,数据库系统一般采用如下图所示的三级模式结构。图中①②处应填写(26),③处应填写(27)。
风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。“建立风险条目检查表”是(18)时的活动,“描述风险的结果”是(19)时的活动。
用等价类划分法设计8位长数字类型用户名登录操作的测试用例,应该分成(44)个等价区间。
对需求说明书评测的内容包括______。①系统定义的目标是否与用户的要求一致②被开发项目的数据流与数据结构是否足够、确定③与所有其他系统交互的重要接口是否都已经描述④主要功能是否已包含在规定的软件范围之内,是否都已充分说明
以下关于软件生命周期的叙述不正确的是______。A.软件生命周期包括以下几个阶段:项目规划、需求定义和需求分析、软件设计、程序编码、软件测试、运行维护B.程序编码阶段是将软件设计的结果转换成计算机可运行的程序代码。为了保证程序的可读性、易维护性和提高
以下类图中,类Classl和Class2之间是()关系。
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则___________(41)是一个大项堆结构,该堆结构用二叉树表示,其高度(或层数)为___________(42)。(41)
随机试题
北美自由贸易区的成员国有()
引起肾的颗粒细胞释放肾素的因素有()(2009年)
免疫复合物所致基底膜损伤是由于中性粒细胞释放下述何种物质引起的
在我国,商业银行是指依照《中华人民共和国商业银行法》和《中华人民共和国公司法》设立的从事()等业务的企业法人。
对国务院各部门和地方各级政府的财政收支,对国家的财政金融机构和企事业组织的财政收支进行审计监督的机关是()。
事业单位要贯彻按劳分配与按生产要素分配,效率优先、兼顾公平的分配原则,扩大()分配自主权,逐步建立重实绩、重贡献,向优秀人才和关键岗位倾斜,形式多样、自主灵活的分配激励机制。
太阳系的小行星带分布在()。
“高原不倒千年骨,告慰炎黄有子孙”与“尽道隋亡为此河,至今千里赖通波”中的“高原”与“河”分别指的是我国的()。
下列对IPv6地址FF60:0:0:0601:BC:0:0:05D7的简化表示中,错误的是
A、Thewomanisconfidenttoimprovestudents’psychologicalproblems.B、Thewomanisapsychologist.C、Themanseemstohavepsy
最新回复
(
0
)