首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明,回答问题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
66
问题
阅读下列说明,回答问题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
软件设计师下午应用技术考试
软考中级
相关试题推荐
针对以下程序段,对于变量c的取值,至少需要(61)个测试用例才能够满足语句覆盖的要求。c=((u8_t*)q->payload)[i];switch(c){caseSLIP_END:sio_send(SLIP_ESC,netif->state);
若关系R、S如下图所示,则R与S自然连接后的属性列数和元组个数分别为(28);π1,4(σ3=6(R×S))=(29)。
从数据库管理系统的角度看,数据库系统一般采用如下图所示的三级模式结构。图中①②处应填写(26),③处应填写(27)。
负载压力性能测试需求分析时,应该选择(63)类型的业务作为测试案例。 ①高吞吐量的业务 ②业务逻辑复杂的业务 ③高商业风险的业务 ④高服务器负载的业务 ⑤批处理的业务
对于提升磁盘I/O性能问题,以下表述正确的是(58)。
对软件可靠性的理解,正确的是(45)。①软件可靠性是指在指定条件下使用时,软件产品维持规定的性能级别的能力②软件可靠性的种种局限是由于随着时间的推移,软件需求和使用方式发生了变化③软件可靠性包括成熟性、有效性、容错性、易恢复性
以下关于白盒测试和黑盒测试的理解,正确是______。A.白盒测试通过对程序内部结构的分析、检测来寻找问题B.白盒测试通过一些表征性的现象、事件、标志来判断内部的运行状态C.单元测试可应用白盒测试方法,集成测试则采用黑盒测试方法D.在软件生命周期各
V模型描述了软件基本的开发过程和测试行为,描述了不同测试阶段与开发过程各阶段的对应关系。其中,集成测试阶段对应的开发阶段是______。A.需求分析阶段B.概要设计阶段C.详细设计阶段D.编码阶段
在C程序中,若表达式中的算术运算对象的类型不同,则需要先统一为相同类型后再进行计算。例如,表达式“a-b”中,若a是双精度浮点型变量,b是整型变量,为了尽可能保证运算精度,通常进行的处理是______。
以下类图中,类Classl和Class2之间是()关系。
随机试题
资本市场也称为中长期资金市场,是以期限在()年以上的金融工具为媒介进行中长期资金融通的市场。
R12不溶于水,设备()。
DoyouthinktheDirectMethodcouldbeusedbyallforeignlanguageteachersatalllevels?Whyorwhynot?
对市场竞争比较激烈的项目产品,应进行营销策略研究,营销策略6P中包括()。
根据现行合同价款的调整要求,承包人采购材料和工程设备的,应在合同中约定主要材料或工程设备价格变化的范围和幅度,如没有约定,则单价变化超过()时,超过部分应做相应的调整。
下列关于产业政策与市场机制关系的叙述正确的有()。
求下列各函数的微分:
形成WebService架构基础的协议不包括______。A.SOAFB.DHCPC.WSDLD.UDDI
支持子程序调用的数据结构是()。
MalnutritionandtheDiseasesofPovertyMalnutritiondisproportionatelyaffectsthoseinsub-SaharanAfrica.Over35percent
最新回复
(
0
)