首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。 【说明】 某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1,m2,…,mn,每项食物mi的营养价值为vi,价格为pi其中i=1,2,…,n,套餐中每项食物至多出现一次。客人常需要一个算法
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。 【说明】 某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1,m2,…,mn,每项食物mi的营养价值为vi,价格为pi其中i=1,2,…,n,套餐中每项食物至多出现一次。客人常需要一个算法
admin
2009-02-01
76
问题
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。
【说明】
某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1,m2,…,mn,每项食物mi的营养价值为vi,价格为pi其中i=1,2,…,n,套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。
1. 【问题1】
下面是用动态规划策略求解该问题的伪代码,请填充其中的空缺(1)、(2)和(3)处。
伪代码中的主要变量说明如下。
n:总的食物项数;
v:营养价值数组,下标从1到n,对应第1到第n项食物的营养价值;
p:价格数组,下标从1到n,对应第1到第n项食物的价格;
M:总价格标准,即套餐的价格不超过M;
x:解向量(数组),下标从1到n,其元素值为0或1,其中元素值为0表示对应的食物不出现在套餐中,元素值为1表示对应的食物出现在套餐中;
nv:n+1行M+1列的二维数组,其中行和列的下标均从0开始,nv
[j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。
伪代码如下:
MaxNutrientValue(n,v,p,M,x)
1 for i=0 to n
2 nv
[0] = 0
3 for j=1 to M
4 nv[0][j]=0
5 for i=1 to n
6 for j=1 to M
7 if j<p
//若食物mi不能加入到套餐中
8 nv
[j] = nv[i-1][j]
9 else if (1)
10 nv
[j]= nv[i-1][j]
11 else
12 nv
[j]= nv[i-1][j-p
] + v
13 j = M
14 for i=n downto 1
15 if (2)
16 x
= 0
17 else
18 x
= 1
19 (3)
20 return x and nv[n][M]
选项
答案
(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]
解析
转载请注明原文地址:https://kaotiyun.com/show/w5DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列流程图:当用判定覆盖法进行测试时,至少需要设计(44)个测试用例。
软件开发人员可以用(18)软件编写和修改程序。
在数据库管理系统中,(13)不属于安全性控制机制。
(12)是指把数据以及操作数据的相关方法组合在同一个单元中,使我们可以把类作为软件中的基本复用单元,提高其内聚度,降低其耦合度。面向对象中的(13)机制是对现实世界中遗传现象的模拟,通过该机制,基类的属性和方法被遗传给派生类。
关于数据库索引,以下表述正确的是(57)。①如果对表创建了索引,那么更新、插入和删除表中的记录都将导致额外的系统开销。②全表扫描一定比使用索引的执行效率低。③在字段选择性很低的情况下适用索引。④一个表创建的索引越多,对系统的性能提升越大。
针对程序段:IF(X>10)AND(Y<20)THEN W=W/A,对于(X,Y)的取值,以下(56)组测试用例能够满足判定覆盖的要求。
对软件可靠性的理解,正确的是(45)。①软件可靠性是指在指定条件下使用时,软件产品维持规定的性能级别的能力②软件可靠性的种种局限是由于随着时间的推移,软件需求和使用方式发生了变化③软件可靠性包括成熟性、有效性、容错性、易恢复性
软件测评相关的标准一般可以分为国际标准、国家标准、行业标准以及企业标准。一般情况下,技术要求最高的是______。A.国际标准B.国家标准C.行业标准D.企业标准
以下关于白盒测试和黑盒测试的理解,正确是______。A.白盒测试通过对程序内部结构的分析、检测来寻找问题B.白盒测试通过一些表征性的现象、事件、标志来判断内部的运行状态C.单元测试可应用白盒测试方法,集成测试则采用黑盒测试方法D.在软件生命周期各
在C程序中,若表达式中的算术运算对象的类型不同,则需要先统一为相同类型后再进行计算。例如,表达式“a-b”中,若a是双精度浮点型变量,b是整型变量,为了尽可能保证运算精度,通常进行的处理是______。
随机试题
关于睾丸功能的叙述,下列错误的是()
下述内容,哪些项不符合实际
患者男性,62岁,大学毕业,医生。患者从5年前开始出现记忆力下降,表现为经常“丢三落四”,说过的话就忘,放的东西找不到。2年前有时外出后找不到家,现在在家里经常找不到自己的房间和卫生间。有时半夜起来东摸西摸,把桌椅搬来搬去。既往体健,否认高血压、糖尿病、卒
A.在注册执业地点签名留样或专用签章备案B.经所在医疗机构培训并考核合格C.经所在机构有处方权的执业医师审核,并签名或加盖专用签章后有效D.对其工作能力认定后授予药师取得麻醉药品和第一类精神药品调剂资格的前提是
企业在生产经营活动中,有时会面临零部件自制还是外购决策问题。假设无论外购还是自制,企业固定成本总额均不变,那么这类问题决策时,一般只考虑()。
(2012年)甲公司是一家上市公司,2011年的利润分配方案如下:每10股送2股并派发现金红利10元(含税),资本公积每10股转增3股。如果股权登记日的股票收盘价为每股25元,则除权(息)日的股票参考价格为()元。
巴拉萨一萨缪尔森效应(Balassa-SamuelsonEffect)
Hezbollahlaunchedthedisturbancebecause
Inbringing【C1】______children,everyparentwatcheseagerlythechild’sacquisitionofeachnew【C2】______--thefirstspokenwo
A、Teenagerswanttobedifferentfromtheirparents.B、Teenagersgrowupinadifferentenvironment.C、Parentsdon’twanttheir
最新回复
(
0
)