信管网每日一练
软件设计师 - 每日一练 导航

软件设计师案例分析每日一练试题(2023/3/16)

2023年03月17日来源:信管网 作者:cnitpm

软件设计师案例分析当天每日一练试题地址:www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总:www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题(2023/3/16)在线测试:www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2023/3/16

点击查看:更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容(2023/3/16)

试题四
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。
【说明】
某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1,m2,…,mn,每项食物mi的营养价值为vi,价格为pi其中i=1,2,…,n,套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。
【问题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[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。
伪代码如下:
MaxNutrientValue(n,v,p,M,x)
1  for i=0  to n
2  nv[i][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[i]  //若食物mi不能加入到套餐中
8  nv[i][j] =  nv[i-1][j]
9  else if   (1)
10  nv[i][j]=  nv[i-1][j]
11  else
12  nv[i][j]=  nv[i-1][j-p[i]]  +  v[i]
13  j = M
14  for i=n downto 1
15  if   (2)
16  x[i] = 0
17  else
18  x[i] = 1
19    (3)
20  return x and nv[n][M]
【问题2】
现有5项食物,每项食物的营养价值和价格如下表所示。

食物营养价值及价格表
若要求总价格不超过100的营养价值最大的套餐,则套餐应包含的食物有  (4)  (用食物项的编码表示),对应的最大营养价值为  (5)  。
【问题3】
问题1中伪代码的时间复杂度为  (6)  (用O符号表示)。



信管网试题答案与解析:www.cnitpm.com/st/2457421374.html

信管网考友试题答案分享:

信管网试题答案与解析:www.cnitpm.com/st/2457421374.html

温馨提示:因考试政策、内容不断变化与调整,信管网提供的以上信息仅供参考,如有异议,请考生以权威部门公布的内容为准!

分享至:

信管网 - 信息系统项目管理专业网站

下载APP-在线学习

培训课程

0元畅享

考试题库

免费资料

客服咨询