考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如图8一11所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了(60)设计策略。考虑0／1背包问题(每件物品或者全部装入背包或者不

admin2019-07-12 25

问题考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如图8一11所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了(60)设计策略。考虑0／1背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包)，求解该实例得到的最大价值分别为(61)。

(61)

选项 A、605和630
B、605和605
C、430和630
D、630和430

答案C

解析本题考查贪心算法和背包问题的知识点。贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。采用0／1背包考虑该问题时，只能放入1、2、3号物品，故总价值为430，采用部分背包可以将物品拆分，故放入1、2、3号物品后还可以将编号4的物品部分的装入，使得背包容量尽量的满，故总容量为630。

转载请注明原文地址:https://kaotiyun.com/show/I6CZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

在进行进度安排时，PERT图不能清晰的描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、……、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2)

在IP协议的数据报报头中，与分片和重新组装无关的字段有__________。

~IPSec的加密和认证过程中所使用的密钥由()机制来生成和分发。

~xDSL技术中，能提供上下行信道非对称传输的是()。

使用白盒测试方法时，确定测试用例应根据__________和指定的覆盖标准。(2010年上半年试题)

ATM网络采用了许多通信量管理技术以避免拥塞的出现，其中(34)是防止网络过载的第一道防线。

根据上述说明，请给出(1)“职员”关系模式的主键和外键。(2)“部门”关系模式的主键和外键。原来的“职员”关系模式存在什么问题?在不增加新关系模式的前提下，请给出修改后的“职员”和“部门”关系模式。

某护士长在领导护士们完成病房护理工作的过程中，注意个人目标和组织目标协调一致，这样护士们的行为趋向统一，对实现组织目标并取得成效非常有益。这种领导方法遵循的领导工作原理是

某机械搅拌澄清池设计流量为400m3／h，水厂自用水量按5％计算，穿孔集水槽为薄壁孔口(流量系数为0．62)，孔口直径为25mm，设计开孔个数为464个，则设计孔口中心线的水头为()m。

在如图所示的电路中，Us单独作用时，电阻R流过的电流I’=1A，消耗的功率P’=5W；Is单独作用时，电阻R流过的电流I’’=2A，电阻尺消耗的功率P’’=20W；则Us和Is同时作用时，电阻R消耗的功率为()。

下列费用中，不应计入设备及工器具购置费的是()。

下列各项属于可以动用期货投资者保障基金的情形有()。

客户评级的评价主体是()。

在担保管理评价工作中，商业银行对保证人的管理评价内容不包括()。

《国家创新驱动发展战略纲要》提出，实现创新驱动按照“坚持双轮驱动、构建一个体系、推动六大转变”进行布局。其中，“双轮”是指()。

有公司采用弹性工作制，更注重效率，而不是压力。(emphasison)

Mostlibrariesrequireyoutoregisterbeforeyouareallowedtoborrowanyoftheirmaterials.Thismeansyouwillprobablybe